Shortest path with obstacles :
Difficulty Level : Medium
Submissions : 1081
Asked In :
Marks :15
: 12 | : 4
You are given an $$$n \times m$$$ integer grid where each cell is either $$$0$$$ (empty) or $$$1$$$ (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Please find the minimum number of steps to walk from the upper left corner $$$(0, 0)$$$ to the lower right corner $$$(n - 1, m - 1)$$$ given that you can eliminate at most $$$k$$$ obstacles. If it is not possible to find such walk, output $$$-1$$$.
The first line of input contains three space separated integers $$$n$$$, $$$m$$$ $$$(1\le n,m \le 40)$$$ and $$$k$$$ $$$(0 \le k \le n \cdot m)$$$ — the dimensions of the grid and the maximum number of obstacles that you can remove respectively.
Each of the next n lines contains m integer. Each integer is either $$$0$$$ or $$$1$$$ and represents one cell of the grid. It's $$$0$$$ if the corresponding cell is empty and $$$1$$$ if the corresponding cell is an obstacle.
Print a single integer — the minimum number of steps required to reach $$$(n-1,m-1)$$$ from $$$(0,0)$$$ or $$$-1$$$ if it is not possible.
5 3 1 000 110 000 011 000
6
3 3 1 011 111 100
-1
In sample testcase $$$1$$$, The shortest path without eliminating any obstacle is $$$10$$$. The shortest path with $$$1$$$ obstacle elimination at position $$$(3,2)$$$ is $$$6$$$. Such path is $$$(0,0) \longrightarrow (0,1) \longrightarrow (0,2) \longrightarrow (1,2) \longrightarrow (2,2) \longrightarrow (3,2) \longrightarrow (4,2)$$$.
In sample testcase $$$2$$$, We need to eliminate at least $$$2$$$ obstacles to find such a walk. Hence we output $$$-1$$$.
