NumberLabyrinthDiv2
SRM 509 · 2010-11-01 · by nV
Problem Statement
The game is played on an R x C board; rows are numbered 0 to R - 1 from top to bottom and columns are numbered 0 to C - 1 from left to right. The cell in row r and column c is said to have coordinates (r, c). Each cell of the board either contains a single-digit number (0 to 9) or is empty. The board is given as
The goal of the game is to get from cell (r1, c1) to cell (r2, c2) with the fewest number of moves. A move is a jump of length d in a horizontal or vertical direction from a cell with a number d; more formally, if Arthur's position is (r, c) and the cell contains a number d, he can move to cell (r - d, c), (r + d, c), (r, c - d), or (r, c + d). Note that an empty cell or a cell with number 0 is a dead-end. Arthur is also not allowed to leave the board at any time.
Furthermore, before performing moves Arthur is allowed to write any single-digit numbers in at most K empty cells.
Given board, r1, c1, r2, c2, and K, return the minimum number of moves Arthur needs to reach the goal. Return -1 if it is impossible to reach the goal.
Constraints
- R and C will each be between 1 and 50, inclusive.
- board will contain exactly R elements.
- Each element of board will contain exactly C characters.
- Each element of board will contain only the following characters: '.', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'.
- r1 and r2 will each be between 0 and R - 1, inclusive.
- c1 and c2 will each be between 0 and C - 1, inclusive.
- (r1, c1) and (r2, c2) will represent different cells.
- K will be between 0 and 50, inclusive.
{"...2",
"....",
"3..."}
0
0
2
3
0
Returns: -1
There is no way to reach the goal because cell (r1, c1) does not contain a number and Arthur is not allowed to write any.
{"...2",
"....",
"3..."}
0
0
2
3
1
Returns: 2
This time the goal is reachable. Two possible ways are: - writing number 3 in cell (0, 0) allowing him to perform moves (0, 0) -> (0, 3) -> (2, 3); - writing number 2 in cell (0, 0) allowing him to perform moves (0 ,0) -> (2, 0) -> (2, 3).
{"...3",
"....",
"2..."}
0
0
2
3
3
Returns: 3
This time it is impossible to reach the goal in two or less moves. However, Arthur can write new numbers in at most 3 cells, which allows him to reach the goal in 3 moves. For example, Arthur can write 2 in cell (0, 0), 2 in cell (0, 2), and 1 in cell (2, 2), enabling him to perform moves (0, 0) -> (0, 2) -> (2, 2) -> (2, 3).
{"55255",
".0.0.",
"..9..",
"..3..",
"3.9.3",
"44.44"}
3
2
4
2
10
Returns: 6
This time the finish cell is right next to the starting cell. However, because of the configuration of the board quite a few moves have to be performed.
{"920909949",
"900020000",
"009019039",
"190299149",
"999990319",
"940229120",
"000409399",
"999119320",
"009939999"}
7
3
1
1
50
Returns: 10
There are lots of dead-ends here, and a large K does not help this time as no cell is empty.
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NumberLabyrinthDiv2 with a public method int getMinimumNumberOfMoves(vector<string> board, int r1, int c1, int r2, int c2, int K) · 88 test cases · 2 s / 256 MB per case