Shortest path with walls you may break

from collections import deque

def shortest_path_breaking(grid, k):
    rows, cols = len(grid), len(grid[0])
    if k >= rows + cols - 3:
        return rows + cols - 2                 # enough to walk straight through anything
    seen = {(0, 0, k)}
    q = deque([(0, 0, k, 0)])                  # (row, col, walls left, steps)
    while q:
        r, c, left, steps = q.popleft()
        if r == rows - 1 and c == cols - 1:
            return steps
        for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= a < rows and 0 <= b < cols:
                nl = left - grid[a][b]         # a wall costs one
                if nl >= 0 and (a, b, nl) not in seen:
                    seen.add((a, b, nl))
                    q.append((a, b, nl, steps + 1))
    return -1

#include <array>
#include <queue>
#include <vector>

int solve(const std::vector<std::vector<int>>& grid, int k) {
    const int rows = grid.size(), cols = grid[0].size();
    if (k >= rows + cols - 3) return rows + cols - 2;            // straight through anything
    std::vector<std::vector<std::vector<bool>>> seen(rows, std::vector<std::vector<bool>>(cols, std::vector<bool>(k + 1, false)));
    std::queue<std::array<int, 4>> q;                            // row, col, walls left, steps
    q.push({0, 0, k, 0});
    seen[0][0][k] = true;
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c, left, steps] = q.front();
        q.pop();
        if (r == rows - 1 && c == cols - 1) return steps;
        for (int d = 0; d < 4; ++d) {
            int a = r + dr[d], b = c + dc[d];
            if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
            int nl = left - grid[a][b];                          // a wall costs one
            if (nl >= 0 && !seen[a][b][nl]) { seen[a][b][nl] = true; q.push({a, b, nl, steps + 1}); }
        }
    }
    return -1;
}

import java.util.*;

class Solution {
    public int shortestPathBreaking(int[][] grid, int k) {
        int rows = grid.length, cols = grid[0].length;
        if (k >= rows + cols - 3) return rows + cols - 2;        // straight through anything
        boolean[][][] seen = new boolean[rows][cols][k + 1];
        ArrayDeque<int[]> q = new ArrayDeque<>();                // row, col, walls left, steps
        q.add(new int[]{0, 0, k, 0});
        seen[0][0][k] = true;
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] s = q.poll();
            if (s[0] == rows - 1 && s[1] == cols - 1) return s[3];
            for (int d = 0; d < 4; d++) {
                int a = s[0] + dr[d], b = s[1] + dc[d];
                if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
                int nl = s[2] - grid[a][b];                      // a wall costs one
                if (nl >= 0 && !seen[a][b][nl]) { seen[a][b][nl] = true; q.add(new int[]{a, b, nl, s[3] + 1}); }
            }
        }
        return -1;
    }
}

function shortestPathBreaking(grid, k) {
  const rows = grid.length, cols = grid[0].length;
  if (k >= rows + cols - 3) return rows + cols - 2;      // straight through anything
  const seen = new Uint8Array(rows * cols * (k + 1));    // state (r, c, walls left)
  const id = (r, c, w) => (r * cols + c) * (k + 1) + w;
  seen[id(0, 0, k)] = 1;
  let ring = [[0, 0, k]];
  for (let steps = 0; ring.length; steps++) {
    const next = [];
    for (const [r, c, left] of ring) {
      if (r === rows - 1 && c === cols - 1) return steps;
      for (const [a, b] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
        if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
        const nl = left - grid[a][b];                     // a wall costs one
        if (nl >= 0 && !seen[id(a, b, nl)]) { seen[id(a, b, nl)] = 1; next.push([a, b, nl]); }
      }
    }
    ring = next;
  }
  return -1;
}

use std::collections::VecDeque;

fn solve<const C: usize>(grid: &[[i64; C]], k: i64) -> i64 {
    let rows = grid.len();
    let k = k as usize;
    if k + 3 >= rows + C {
        return (rows + C - 2) as i64;                            // straight through anything
    }
    let mut seen = vec![vec![vec![false; k + 1]; C]; rows];
    let mut q = VecDeque::from([(0usize, 0usize, k, 0i64)]);     // row, col, walls left, steps
    seen[0][0][k] = true;
    while let Some((r, c, left, steps)) = q.pop_front() {
        if r == rows - 1 && c == C - 1 {
            return steps;
        }
        let around = [(r + 1, c), (r.wrapping_sub(1), c), (r, c + 1), (r, c.wrapping_sub(1))];
        for (a, b) in around {
            if a >= rows || b >= C {
                continue;
            }
            let wall = grid[a][b] as usize;
            if left < wall {
                continue;                                        // no wall left to break
            }
            let nl = left - wall;
            if !seen[a][b][nl] {
                seen[a][b][nl] = true;
                q.push_back((a, b, nl, steps + 1));
            }
        }
    }
    -1
}

import qualified Data.Set as S
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: [[Int]] -> Int -> Int
solve grid k
  | k >= rows + cols - 3 = rows + cols - 2              -- straight through anything
  | otherwise = bfs (Q.singleton ((0, 0, k), 0)) (S.singleton (0, 0, k))
  where
    rows = length grid
    cols = length (head grid)
    cell r c = (grid !! r) !! c
    -- states are (row, col, walls left)
    bfs Empty _ = -1
    bfs (((r, c, left), steps) :<| q) seen
      | r == rows - 1 && c == cols - 1 = steps
      | otherwise =
          let next = [ (a, b, left - cell a b)
                     | (a, b) <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
                     , a >= 0, b >= 0, a < rows, b < cols
                     , left - cell a b >= 0
                     , not (S.member (a, b, left - cell a b) seen) ]
          in bfs (foldl (|>) q [(s, steps + 1) | s <- next]) (foldr S.insert seen next)