DucksAlignment
SRM 526 · 2011-05-25 · by fushar
SRM 526 · 2011-05-25 · by fushar · Brute Force, Greedy
Problem Statement
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 String[] 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.
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.
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
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DucksAlignment with a public method int minimumTime(vector<string> grid) · 68 test cases · 2 s / 256 MB per case