Shortest path through a grid

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == '#' or grid[-1][-1] == '#':
        return -1
    dist = [[-1] * cols for _ in range(rows)]
    dist[0][0] = 0
    q = deque([(0, 0)])
    while q:
        i, j = q.popleft()
        if (i, j) == (rows - 1, cols - 1):
            return dist[i][j]           # BFS reaches every cell first by a shortest path
        for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= a < rows and 0 <= b < cols and grid[a][b] == '.' and dist[a][b] < 0:
                dist[a][b] = dist[i][j] + 1     # mark on enqueue
                q.append((a, b))
    return -1

#include <queue>
#include <string>
#include <utility>
#include <vector>

int solve(const std::vector<std::string>& grid) {
    const int rows = grid.size(), cols = grid[0].size();
    if (grid[0][0] == '#' || grid[rows - 1][cols - 1] == '#') return -1;
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    std::queue<std::pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        if (i == rows - 1 && j == cols - 1) return dist[i][j];
        for (int k = 0; k < 4; ++k) {
            const int a = i + dr[k], b = j + dc[k];
            if (a >= 0 && a < rows && b >= 0 && b < cols && grid[a][b] == '.' && dist[a][b] < 0) {
                dist[a][b] = dist[i][j] + 1;            // mark on enqueue
                q.push({a, b});
            }
        }
    }
    return -1;
}

class Solution {
    public int shortestPath(String[] grid) {
        int rows = grid.length, cols = grid[0].length();
        if (grid[0].charAt(0) == '#' || grid[rows - 1].charAt(cols - 1) == '#') return -1;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) java.util.Arrays.fill(row, -1);
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        java.util.ArrayDeque<int[]> q = new java.util.ArrayDeque<>();
        dist[0][0] = 0;
        q.add(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int i = cell[0], j = cell[1];
            if (i == rows - 1 && j == cols - 1) return dist[i][j];
            for (int k = 0; k < 4; k++) {
                int a = i + dr[k], b = j + dc[k];
                if (a >= 0 && a < rows && b >= 0 && b < cols && grid[a].charAt(b) == '.' && dist[a][b] < 0) {
                    dist[a][b] = dist[i][j] + 1;        // mark on enqueue
                    q.add(new int[]{a, b});
                }
            }
        }
        return -1;
    }
}

function shortestPath(grid) {
  const rows = grid.length, cols = grid[0].length;
  if (grid[0][0] === '#' || grid[rows - 1][cols - 1] === '#') return -1;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  dist[0][0] = 0;
  const q = [[0, 0]];
  for (let head = 0; head < q.length; head++) {      // an index instead of shift(): O(1) per pop
    const [i, j] = q[head];
    if (i === rows - 1 && j === cols - 1) return dist[i][j];
    for (const [a, b] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
      if (a >= 0 && a < rows && b >= 0 && b < cols && grid[a][b] === '.' && dist[a][b] < 0) {
        dist[a][b] = dist[i][j] + 1;                // mark on enqueue
        q.push([a, b]);
      }
    }
  }
  return -1;
}

use std::collections::VecDeque;

fn solve(grid: &[&str]) -> i64 {
    let g: Vec<&[u8]> = grid.iter().map(|row| row.as_bytes()).collect();
    let (rows, cols) = (g.len(), g[0].len());
    if g[0][0] == b'#' || g[rows - 1][cols - 1] == b'#' {
        return -1;
    }
    let mut dist = vec![vec![-1i64; cols]; rows];
    dist[0][0] = 0;
    let mut q = VecDeque::from([(0usize, 0usize)]);
    while let Some((i, j)) = q.pop_front() {
        if i == rows - 1 && j == cols - 1 {
            return dist[i][j];
        }
        let mut next = Vec::with_capacity(4);
        if i > 0 { next.push((i - 1, j)); }
        if i + 1 < rows { next.push((i + 1, j)); }
        if j > 0 { next.push((i, j - 1)); }
        if j + 1 < cols { next.push((i, j + 1)); }
        for (a, b) in next {
            if g[a][b] == b'.' && dist[a][b] < 0 {
                dist[a][b] = dist[i][j] + 1;            // mark on enqueue
                q.push_back((a, b));
            }
        }
    }
    -1
}

import qualified Data.Set as S

-- Breadth-first search one ring at a time; the ring number is the distance.
solve :: [String] -> Int
solve grid
  | not (open (0, 0)) || not (open goal) = -1
  | otherwise = go 0 [(0, 0)] (S.singleton (0, 0))
  where
    rows = length grid
    cols = length (head grid)
    goal = (rows - 1, cols - 1)
    cells = S.fromList [(r, c) | (r, row) <- zip [0 ..] grid, (c, ch) <- zip [0 ..] row, ch == '.']
    open q = q `S.member` cells
    go _ [] _ = -1
    go d ring seen
      | goal `elem` ring = d
      | otherwise =
          let next = S.toList (S.fromList [q | (r, c) <- ring, q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], open q, not (q `S.member` seen)])
          in go (d + 1) next (foldr S.insert seen next)