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.

Examples

Example 1

5×3 · k=1 · 6 moves

Output: 6 moves

Example 2

3×3 · k=1 · no path

Output: no path (-1)

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.