Escape the Zombie Apocalypse - OYO Prism Online Assessment NSUT

Problem Preview

"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`. ### Input Format * The first line contains two integers `N` and `M` — the dimensions of the grid. * The next `N` lines each contain `M` integers describing the grid. * The last line contains two integers `sr` and `sc` — the starting coordinates. ### Output Format Print a single integer — the minimum number of moves required to reach the exit, or `-1` if it is impossible. ### Constraints * `1 ≤ N, M ≤ 1000` * `grid[i][j] ∈ {0,1,2,3}` * Exactly one cell contains `3`. * `0 ≤ sr < N` * `0 ≤ sc < M` * The starting cell is guaranteed not to contain `1` or `2`. ### Sample Input 1 ``` 4 5 0 0 0 1 3 1 1 0 1 0 0 0 0 0 0 2 1 1 1 0 2 0 ``` ### Sample Output 1 ``` 6 ``` ### Explanation One shortest path is: `(2,0) → (2,1) → (2,2) → (1,2) → (0,2) → (0,1) → (0,4)` (avoiding blocked cells), requiring **6** moves. --- ### Sample Input 2 ``` 3 3 0 1 3 1 1 1 0 0 0 2 0 ``` ### Sample Output 2 ``` -1 ``` ### Explanation The exit is completely blocked by walls, so it cannot be reached. ---"