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.