EllysChessboard
SRM 577 · 2012-12-13 · by rng_58
SRM 577 · 2012-12-13 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
Elly has a standard chessboard, divided into 8 by 8 unit square cells.
She wants to place pebbles onto some of the cells.
You are given a String[] board.
The j-th character of the i-th element of board is '#' if she wants to put a pebble onto the cell (i, j), and it is '.' otherwise.
Initially the chessboard doesn't contain any pebbles. Elly places the pebbles one by one. The cost of adding a pebble is defined as follows. If this is the first pebble to be placed (i.e., the board is empty), it can be placed for free. Otherwise, the cost is the Manhattan distance (see Notes for the definition) to the most distant pebble that has already been placed on the board.
Return the minimal total cost of placing a pebble onto each chosen cell.
Initially the chessboard doesn't contain any pebbles. Elly places the pebbles one by one. The cost of adding a pebble is defined as follows. If this is the first pebble to be placed (i.e., the board is empty), it can be placed for free. Otherwise, the cost is the Manhattan distance (see Notes for the definition) to the most distant pebble that has already been placed on the board.
Return the minimal total cost of placing a pebble onto each chosen cell.
Notes
- The Manhattan distance between the cell (x1, y1) and the cell (x2, y2) is defined as |x1-x2| + |y1-y2|, where || denotes absolute value.
Constraints
- board will contain exactly 8 elements.
- Each element of board will contain exactly 8 characters.
- Each character in board will be either '#' or '.'.
Examples
0)
{"........",
"........",
"...#....",
".#......",
".......#",
"........",
"........",
"........"}
Returns: 10
Elly wants to put pebbles on three cells: (2, 3), (3, 1), and (4, 7). One of the optimal ways to do this is as follows: First, put a pebble to (2, 3). It costs nothing. Next, put a pebble to (3, 1). It costs |2-3| + |3-1| = 3. Next, put a pebble to (4, 7). The Manhattan distance between (4, 7) and (2, 3) is 6, and the Manhattan distance between (4, 7) and (3, 1) is 7, so the cost is max(6, 7) = 7. The total cost is 0 + 3 + 7 = 10.
1)
{"........",
"........",
"........",
"........",
"........",
"........",
"........",
"........"}
Returns: 0
2)
{"........", "........", "........", "........", "........", "........", "........", "......#."}
Returns: 0
3)
{"........", "........", "........", ".......#", "....#...", "........", "........", "........"}
Returns: 4
4)
{"........", "........", "........", "........", "........", "........", "...#....", "......##"}
Returns: 6
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysChessboard with a public method int minCost(vector<string> board) · 72 test cases · 2 s / 256 MB per case