Shortest Path in a Grid with Obstacles Elimination | by Algorithms Digest | Algorithms Digest | Medium
Interesting techniques, strategies and problems for competitive and Leetcode programming explained in an intuitive manner. Follow publication Algorithms Digest highlighted Algorithms Digest highlighted 149 1 Listen Share This blog post covers the Shortest Path In A Grid With Obstacles Elimination problem on Leetcode. This problem illustrates how a standard graph traversal algorithm can solve a tricky problem if we smartly encode multiple parameters into the graph state. You are given an m x n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such a walk return -1. We need to find the shortest path from the top-left corner to the bottom-right corner. The only condition is that some cells are blocked and we are