Shortest Grid Path with Limited Blocked Cells

You are given an m x n integer matrix grid in which every cell is either 0 (empty) or 1 (blocked), together with an integer k.

Starting from the top-left cell (0, 0), you may move one step to an adjacent cell in any of the four directions (up, down, left, or right). Passing through a blocked cell is allowed but consumes part of your budget: over the whole walk you may enter at most k blocked cells.

Return the minimum number of steps needed to reach the bottom-right cell (m - 1, n - 1) without entering more than k blocked cells. If no such walk exists, return -1.

The corners (0, 0) and (m - 1, n - 1) are always empty.

Examples

Example 1

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation: With no blocked cell entered the shortest walk has length 10.
Entering one blocked cell at (3, 2) allows the walk
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2), which has length 6.

Example 2

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: Reaching the bottom-right cell requires entering at least two
blocked cells, which exceeds the budget of k = 1, so no valid walk exists.