Hard · Graphs

Shortest Path in a Grid With Obstacles Elimination

Given an m × n grid where 0 is an empty cell and 1 is an obstacle, and an integer k, return the minimum number of up/down/left/right moves from the top-left cell to the bottom-right cell when you may eliminate at most k obstacles, or −1 if no such walk exists.

5×3 · k=1 · 6 moves

3×3 · k=1 · no path