Shortest Four-Direction Route With an Obstacle Budget

### Problem In the binary grid, 0 is empty and 1 is an obstacle. Starting at the empty top-left cell, move up,down,left or right one cell per step. You may eliminate at most k obstacles to walk through them. Return the minimum steps to the empty bottom-right cell, or -1 if impossible. ```cpp class Solution { public: int shortestPath(vector<vector<int>>& grid, int k); }; ``` ### Examples **Example 1:** ```text Input: grid = [[0,1,0]], k = 1 Output: 2 Explanation: Remove the middle obstacle and take two rightward steps. ``` **Example 2:** ```text Input: grid = [[0,1,1],[1,1,1],[1,1,0]], k = 1 Output: -1 Explanation: Every shortest corner route has three internal obstacle cells, and any longer route cannot avoid needing more than one. ``` ### Constraints - The rectangular grid has 1 to 40 rows and 1 to 40 columns. - `1 <= k <= rows*cols`. - Entries are 0 or 1, and both endpoint cells are 0. ### Contract considerations Endpoint cells are guaranteed empty. Obstacle removal does not authorize diagonal moves. ```hint Read the boundary condition Must every permitted elimination be used, and are diagonal moves allowed? ``` ### Boundary reminders Endpoint cells are guaranteed empty. Obstacle removal does not authorize diagonal moves.