Problem C
Breaking Maze
Christian starts at the top-left corner of a maze, and Grace starts at the bottom-right corner. The maze is represented as a 2D grid of size $N \times M$, where each cell contains a non-negative cost: $0$ represents an open space, and any positive number represents a wall or obstacle.
Christian wants to move from the top-left cell $(0, 0)$ to the bottom-right cell $(N-1, M-1)$ using the minimum number of steps. However, the sum of the costs of all cells along the path (including the start and end cells) cannot exceed his total strength $S$.
Christian can move up, down, left, or right to adjacent cells. A path is valid only if the cumulative cost along the path never exceeds $S$.
Input
-
The first line contains three integers $N$, $M$, and $S$ ($1 \le N, M \le 100$, $0 \le S \le 10{,}000$) — the dimensions of the maze and Christian’s total strength.
-
Each of the next $N$ lines contains $M$ integers $x$ ($0 \le x \le 1000$), representing the cost of each cell in the maze.
Output
-
Print a single integer — the length of the shortest path from $(0, 0)$ to $(N-1, M-1)$ whose cumulative cost does not exceed $S$.
-
If no such path exists, print $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 10 11 0 2 5 1 0 2 1 1 0 0 0 0 3 1 0 2 1 1 0 0 0 1 0 1 5 2 1 1 0 0 0 6 0 1 5 0 6 1 0 0 0 1 0 1 5 2 7 1 0 0 9 0 0 1 0 5 1 0 0 0 0 2 1 1 5 2 1 1 9 0 0 2 1 1 0 2 1 1 9 0 0 2 1 1 0 21 1 1 0 2 0 2 1 1 0 2 1 1 5 0 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 5 63 0 1 0 0 100 9 0 0 0 100 9 0 0 0 100 9 100 100 9 0 9 9 9 9 0 |
8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 12 210 1 1 1 1 1 150 50 1 1 1 50 50 50 50 50 50 1 150 50 1 1 1 50 50 50 50 50 50 1 150 150 1 1 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 1 1 1 250 1 50 50 50 50 50 50 50 50 50 250 250 1 50 50 50 50 50 50 50 50 50 250 250 1 1 1 50 50 50 50 50 50 50 50 50 50 50 1 50 50 50 50 50 50 50 50 50 50 50 1 |
26 |
| Sample Input 4 | Sample Output 4 |
|---|---|
10 12 27 1 1 1 1 1 150 50 1 1 1 50 50 50 50 50 50 1 150 50 1 1 1 50 50 50 50 50 50 1 150 150 1 1 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 1 1 1 250 1 50 50 50 50 50 50 50 50 50 250 250 1 50 50 50 50 50 50 50 50 50 250 250 1 1 1 50 50 50 50 50 50 50 50 50 50 50 1 50 50 50 50 50 50 50 50 50 50 50 1 |
26 |
| Sample Input 5 | Sample Output 5 |
|---|---|
10 12 26 1 1 1 1 1 150 50 1 1 1 50 50 50 50 50 50 1 150 50 1 1 1 50 50 50 50 50 50 1 150 150 1 1 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 150 50 1 250 1 50 50 50 50 50 50 1 1 1 1 250 1 50 50 50 50 50 50 50 50 50 250 250 1 50 50 50 50 50 50 50 50 50 250 250 1 1 1 50 50 50 50 50 50 50 50 50 50 50 1 50 50 50 50 50 50 50 50 50 50 50 1 |
-1 |
