PROBLEM STATEMENT
Mr. Dengklek has a rectangular farm conveniently divided into a grid of unit squares. At this
moment, each unit square contains at most one duck. Moreover, each row and column of the farm also
contains at most one duck. You are given a vector grid. The j-th character of the i-th
element of grid will be 'o' if there is exactly one duck in square (i, j), i.e., row i column j,
or '.' if there is no duck in that square.
Today, Mr. Dengklek wants to align the ducks so that the ducks form a contiguous line. More
precisely, assume that there are N ducks on the farm. After the alignment, the ducks must either
occupy N contiguous squares in some row or N contiguous squares in some column. To accomplish
that, he will move the ducks one at a time. To move a duck in square (a, b) to another empty
square (c, d), he needs |a-c| + |b-d| seconds, where |x| denotes the absolute value of x. Mr.
Dengklek can always move any duck to any empty square he desires - the other ducks are not
obstacles.
Return the minimum time in seconds Mr. Dengklek needs to align the ducks. Note that restrictions
imposed on the initial placement of ducks guarantee that a proper alignment is always possible.
DEFINITION
Class:DucksAlignment
Method:minimumTime
Parameters:vector
Returns:int
Method signature:int minimumTime(vector grid)
CONSTRAINTS
-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will contain between 1 and 50 characters, inclusive.
-All elements of grid will contain the same number of characters.
-Each character of grid will be either 'o' or '.'.
-Each row in grid will contain at most one character 'o'.
-Each column in grid will contain at most one character 'o'.
-grid will contain at least one character 'o'.
EXAMPLES
0)
{".o",
"o."}
Returns: 1
Move either duck to an adjacent empty square.
1)
{".o...",
"..o..",
"....o"}
Returns: 3
One of the solutions is: move the the duck in the first row one square to the right, and then move
the duck in the last row two squares to the left.
2)
{"o..........",
"..o........",
".......o...",
"...........",
"...........",
"...........",
"........o..",
"..........."}
Returns: 16
Align all ducks in the second row.
3)
{".........",
"....o....",
"........."}
Returns: 0
4)
{"...o..........................",
"............................o.",
".o............................",
"............o.................",
".................o............",
"......................o.......",
"......o.......................",
"....o.........................",
"...............o..............",
".......................o......",
"...........................o..",
".......o......................"}
Returns: 99
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.