NumberLabyrinthDiv1
SRM 509 · 2010-11-01 · by nV
Problem Statement
The game is played on an infinitely large grid; columns are numbered 0, 1, 2, .. from left to right and rows are numbered 0, 1, 2, .. from bottom to top. The cell in column x and row y is said to have coordinates (x, y). Each cell of the board either contains a positive integer or is empty. There are exactly N cells that contain numbers and their descriptions are given as
The goal of the game is to get from cell (0, 0) to cell (xFinish, yFinish) by performing valid moves. A valid 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 (x, y) and the cell contains a number d, he can move to cell (x - d, y), (x + d, y), (x, y - d), or (x, y + d). Note that an empty cell is a dead-end. Arthur is also not allowed to leave the board at any time, i.e., enter a cell (x, y) where x or y (or both) are negative.
Furthermore, before performing moves Arthur is allowed to write any positive integers in at most K empty cells.
Arthur of course wants to reach the goal of the game with the shortest possible path, i.e., the smallest sum of the lengths of jumps that lead from (0, 0) to (xFinish, yFinish).
However, finding a single shortest path in not a difficult task for Arthur. Thus, he is going to find all possible shortest paths. Given X, Y, val, xFinish, yFinish, and K, return the number of different shortest paths Arthur can obtain. Two paths are cosidered different if their respective sequences of jumps are different. Two jumps are different if they have different length or different direction. This number may be very big, so return it modulo 1,000,000,009. If no path exists return 0.
Constraints
- N will be between 0 and 40, inclusive.
- X, Y, and val will each contain exactly N elements.
- Each element of X, Y, and val will be between 1 and 1000000 (10^6), inclusive.
- xFinish and yFinish will each be between 1 and 1000000 (10^6), inclusive.
- K will be between 0 and 10, inclusive.
- All coordinates (X[i], Y[i]) will be distinct and different from (xFinish, yFinish).
{}
{}
{}
3
3
2
Returns: 2
There is no way to reach the finish cell writing numbers in less than two cells. However, the finish can be reached by writing numbers in exactly two cells. The shortest possible path in this case is 6 and that can be obtained in two ways: - writing 3 in cell (0, 0) and 3 in cell (0, 3), allowing him to perform jumps (0, 0) -> (0, 3) -> (3, 3); - writing 3 in cell (0, 0) and 3 in cell (3, 0), allowing him to perform jumps (0, 0) -> (3, 0) -> (3, 3).
{}
{}
{}
3
3
3
Returns: 14
The same situation as in the previous example, but this time there are 12 more paths possible if numbers are written in three cells. For example, Arthur can write 2 in cell (0, 0), 3 in cell (0, 2), and 1 in cell (3, 2) to enable path (0, 0) -> (0, 2) -> (3, 2) -> (3, 3).
{2}
{2}
{1}
3
3
3
Returns: 18
This time one cell already contains a number enabling 4 new shortest paths.
{1, 3, 6}
{1, 3, 6}
{2, 2, 2}
5
5
4
Returns: 210
{1, 19, 20, 21, 21, 21, 20, 19, 19}
{1, 11, 11, 11, 10, 9, 9, 9, 10}
{1, 2, 2, 2, 2, 2, 2, 2, 2}
20
10
4
Returns: 1778
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NumberLabyrinthDiv1 with a public method int getNumberOfPaths(vector<int> X, vector<int> Y, vector<int> val, int xFinish, int yFinish, int K) · 113 test cases · 2 s / 256 MB per case