You are trapped inside a city during a zombie outbreak. The city is represented as a rectangular grid consisting of N rows and M columns.
Each cell of the grid contains one of the following values:
0 — An empty cell that can be traversed.1 — A wall that cannot be crossed.2 — A zombie-infected cell that cannot be entered.3 — The only exit from the city.Your starting position is given as (sr, sc).
From any cell, you may move to one of its four adjacent cells (up, down, left, or right), provided the destination cell lies inside the grid and is not blocked.
Determine the minimum number of moves required to reach the exit. If the exit cannot be reached, print -1.
N and M — the dimensions of the grid.N lines each contain M integers describing the grid.sr and sc — the starting coordinates.Print a single integer — the minimum number of moves required to reach the exit, or -1 if it is impossible.
1 ≤ N, M ≤ 1000grid[i][j] ∈ {0,1,2,3}3.0 ≤ sr < N0 ≤ sc < M1 or 2.4 5
0 0 0 1 3
1 1 0 1 0
0 0 0 0 0
2 1 1 1 0
2 0
6
One shortest path is:
(2,0) → (2,1) → (2,2) → (1,2) → (0,2) → (0,1) → (0,4) (avoiding blocked cells), requiring 6 moves.
3 3
0 1 3
1 1 1
0 0 0
2 0
-1
The exit is completely blocked by walls, so it cannot be reached.
Amazon • Pending