网格图 · 多源 BFS

from collections import deque

def multi_source_bfs(grid: list[list[int]], is_source, can_walk) -> list[list[int]]:
    """
    多源 BFS 通用骨架。
    is_source(grid, i, j)：(i, j) 是否是起点
    can_walk(grid, i, j)：(i, j) 是否可走（非障碍）
    返回 dist 二维数组；不可达记 -1。
    """
    m, n = len(grid), len(grid[0])
    dist = [[-1] * n for _ in range(m)]
    q = deque()
    # 1. 第一遍扫整张网格：所有起点一次性入队，距离 0
    for i in range(m):
        for j in range(n):
            if is_source(grid, i, j):
                dist[i][j] = 0
                q.append((i, j))
    # 2. 标准 BFS 按层扩张
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if (0 <= ni < m and 0 <= nj < n
                    and dist[ni][nj] == -1                # 3. 入队即定距，未访问才进
                    and can_walk(grid, ni, nj)):
                dist[ni][nj] = dist[i][j] + 1             # 4. 邻居距离 = 当前 + 1
                q.append((ni, nj))
    return dist

import java.util.*;

public int[][] multiSourceBFS(int[][] grid,
                              java.util.function.BiPredicate<Integer, Integer> isSource,
                              java.util.function.BiPredicate<Integer, Integer> canWalk) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, -1);
    Deque<int[]> q = new ArrayDeque<>();
    // 1. 起点一次性入队
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isSource.test(i, j)) {
                dist[i][j] = 0;
                q.offer(new int[]{i, j});
            }
        }
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    // 2. 标准 BFS 按层扩张
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int i = cur[0], j = cur[1];
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n
                    && dist[ni][nj] == -1                  // 3. 入队即定距
                    && canWalk.test(ni, nj)) {
                dist[ni][nj] = dist[i][j] + 1;             // 4. 邻居距离 = 当前 + 1
                q.offer(new int[]{ni, nj});
            }
        }
    }
    return dist;
}

vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid,
                                   function<bool(int, int)> isSource,
                                   function<bool(int, int)> canWalk) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int, int>> q;
    // 1. 起点一次性入队
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isSource(i, j)) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    // 2. 标准 BFS 按层扩张
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto& d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
                dist[ni][nj] == -1 &&                       // 3. 入队即定距
                canWalk(ni, nj)) {
                dist[ni][nj] = dist[i][j] + 1;              // 4. 邻居距离 = 当前 + 1
                q.push({ni, nj});
            }
        }
    }
    return dist;
}

from collections import deque

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        # 第一遍扫一遍，腐烂橘子入队、统计新鲜橘子数
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j, 0))                # (i, j, 当前分钟)
                elif grid[i][j] == 1:
                    fresh += 1

        minutes = 0
        while q:
            i, j, t = q.popleft()
            minutes = t
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    grid[ni][nj] = 2                   # 入队即染色
                    fresh -= 1
                    q.append((ni, nj, t + 1))

        return minutes if fresh == 0 else -1

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        int fresh = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) q.offer(new int[]{i, j, 0});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        int minutes = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int i = cur[0], j = cur[1], t = cur[2];
            minutes = t;
            for (int[] d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    fresh--;
                    q.offer(new int[]{ni, nj, t + 1});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<tuple<int, int, int>> q;
        int fresh = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) q.push({i, j, 0});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        int minutes = 0;
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.empty()) {
            auto [i, j, t] = q.front();
            q.pop();
            minutes = t;
            for (auto& d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;                  // 入队即染色
                    fresh--;
                    q.push({ni, nj, t + 1});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
};