分享丨【算法题单】网格图（DFS/BFS/综合应用）

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。原文链接：https://leetcode.cn/circle/discuss/YiXPXW/

网格图题单 DFS BFS 网格图题目图论灵茶山艾府灵神灵神题单

小小贪吃蛇，移动花样多。平移加旋转，为把迷宫破。代码复代码，bug 何其多。六步化一步，AC 定我夺。 —— 1210. 穿过迷宫的最少移动次数

一、网格图 DFS

适用于需要计算连通块个数、大小的题目。

部分题目做法不止一种，也可以用 BFS 或并查集解决。

二叉树 DFS 与网格图 DFS 的区别：

	二叉树	网格图
递归入口	根节点	网格图的某个格子
递归方向	左儿子和右儿子	一般为左右上下的相邻格子
递归边界	空节点（或者叶节点）	出界、遇到障碍或者已访问

模板（计算每个连通块的大小）：

# 返回网格图 grid 每个连通块的大小
# 时间复杂度 O(mn)
def dfsGrid(grid: List[List[str]]) -> List[int]:
    m, n = len(grid), len(grid[0])
    vis = [[False] * n for _ in range(m)]

    # 返回当前连通块的大小
    def dfs(i: int, j: int) -> int:
        vis[i][j] = True
        size = 1
        for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 左右上下
            # 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and not vis[x][y]:
                size += dfs(x, y)
        return size

    comp_size = []
    for i, row in enumerate(grid):
        for j, ch in enumerate(row):
            if ch != '.' or vis[i][j]:  # ch != '.' 根据题意修改
                continue
            size = dfs(i, j)
            comp_size.append(size)
    return comp_size

java

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

    // 返回网格图 grid 每个连通块的大小
    // 时间复杂度 O(mn)
    public List<Integer> dfsGrid(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];

        List<Integer> compSize = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '.' || vis[i][j]) { // grid[i][j] != '.' 根据题意修改
                    continue;
                }
                int size = dfs(i, j, grid, vis);
                compSize.add(size);
            }
        }
        return compSize;
    }

    // 返回当前连通块的大小
    private int dfs(int i, int j, char[][] grid, boolean[][] vis) {
        vis[i][j] = true;
        int size = 1;
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            // 这里 grid[x][y] == '.' 根据题意修改
            if (0 <= x && x < grid.length && 0 <= y && y < grid[x].length && grid[x][y] == '.' && !vis[x][y]) {
                size += dfs(x, y, grid, vis);
            }
        }
        return size;
    }
}

cpp

constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

// 返回网格图 grid 每个连通块的大小
// 时间复杂度 O(mn)
vector<int> dfsGrid(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector vis(m, vector<int8_t>(n));

    // 返回当前连通块的大小
    auto dfs = [&](this auto&& dfs, int i, int j) -> int {
        vis[i][j] = true;
        int size = 1;
        for (auto [dx, dy] : DIRS) {
            int x = i + dx, y = j + dy;
            // 这里 grid[x][y] == '.' 根据题意修改
            if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '.' && !vis[x][y]) {
                size += dfs(x, y);
            }
        }
        return size;
    };

    vector<int> comp_size;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != '.' || vis[i][j]) { // grid[i][j] != '.' 根据题意修改
                continue;
            }
            int size = dfs(i, j);
            comp_size.push_back(size);
        }
    }
    return comp_size;
}

type pair struct{ x, y int }
var dirs = []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下

// 返回网格图 grid 每个连通块的大小
// 时间复杂度 O(mn)
func dfsGrid(grid [][]byte) (compSize []int) {
    m, n := len(grid), len(grid[0])
    vis := make([][]bool, m)
    for i := range vis {
        vis[i] = make([]bool, n)
    }

    // 返回当前连通块的大小
    var dfs func(int, int) int
    dfs = func(i, j int) int {
        vis[i][j] = true
        size := 1
        for _, d := range dirs {
            x, y := i+d.x, j+d.y
            // 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '.' && !vis[x][y] {
                size += dfs(x, y)
            }
        }
        return size
    }

    for i, row := range grid {
        for j, ch := range row {
            if ch != '.' || vis[i][j] { // ch != '.' 根据题意修改
                continue
            }
            size := dfs(i, j)
            compSize = append(compSize, size)
        }
    }
    return
}

思维扩展：

1970. 你能穿过矩阵的最后一天 2124 做法不止一种

二、网格图 BFS

适用于需要计算最短距离（最短路）的题目。

DFS 是不撞南墙不回头；BFS 是往水塘中扔石头（起点），荡起一圈圈涟漪（先访问近的，再访问远的）。

模板（单源最短路）：

# 返回从 (start_x, start_y) 出发，到其余格子的最短距离
# 时间复杂度 O(mn)
def bfsGrid(grid: List[List[str]], start_x: int, start_y: int) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    dis = [[-1] * n for _ in range(m)]

    dis[start_x][start_y] = 0
    q = deque([(start_x, start_y)])

    while q:
        i, j = q.popleft()
        for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 左右上下
            # 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and dis[x][y] < 0:
                dis[x][y] = dis[i][j] + 1
                q.append((x, y))

    return dis

java

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

    // 返回从 (startX, startY) 出发，到其余格子的最短距离
    // 时间复杂度 O(mn)
    public int[][] bfsGrid(char[][] grid, int startX, int startY) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dis = new int[m][n];
        for (int[] row : dis) {
            Arrays.fill(row, -1);
        }

        Queue<int[]> q = new ArrayDeque<>();
        dis[startX][startY] = 0;
        q.offer(new int[]{startX, startY});

        while (!q.isEmpty()) {
            int[] p = q.poll();
            int i = p[0];
            int j = p[1];
            for (int[] dir : DIRS) {
                int x = i + dir[0];
                int y = j + dir[1];
                // 这里 grid[x][y] == '.' 根据题意修改
                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '.' && dis[x][y] < 0) {
                    dis[x][y] = dis[i][j] + 1;
                    q.offer(new int[]{x, y});
                }
            }
        }

        return dis;
    }
}

cpp

constexpr int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下

// 返回从 (start_x, start_y) 出发，到其余格子的最短距离
// 时间复杂度 O(mn)
vector<vector<int>> bfsGrid(vector<vector<char>>& grid, int start_x, int start_y) {
    int m = grid.size(), n = grid[0].size();
    vector dis(m, vector<int>(n, -1));
    queue<pair<int, int>> q;

    dis[start_x][start_y] = 0;
    q.emplace(start_x, start_y);

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto [dx, dy] : DIRS) {
            int x = i + dx, y = j + dy;
            // 这里 grid[x][y] == '.' 根据题意修改
            if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '.' && dis[x][y] < 0) {
                dis[x][y] = dis[i][j] + 1;
                q.emplace(x, y);
            }
        }
    }

    return dis;
}

type pair struct{ x, y int }
var dirs = []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下

// 返回从 (startX, startY) 出发，到其余格子的最短距离
// 时间复杂度 O(mn)
func bfsGrid(grid [][]byte, startX, startY int) [][]int {
    m, n := len(grid), len(grid[0])
    dis := make([][]int, m)
    for i := range dis {
        dis[i] = make([]int, n)
        for j := range dis[i] {
            dis[i][j] = -1
        }
    }

    dis[startX][startY] = 0
    q := []pair{{startX, startY}}

    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, d := range dirs {
            x, y := p.x+d.x, p.y+d.y
            // 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '.' && dis[x][y] < 0 {
                dis[x][y] = dis[p.x][p.y] + 1
                q = append(q, pair{x, y})
            }
        }
    }

    return dis
}

三、网格图 0-1 BFS

边权只有 $0$ 和 $1$ 的题目，也可以用 BFS 做。

四、网格图 Dijkstra

见图论题单中的「§3.1 单源最短路：Dijkstra 算法」，我标记了网格图的题目。

五、综合应用

思考题

对于 $m$ 行 $n$ 列的网格图，BFS 的队列最多消耗多少空间？DFS 的递归栈最多消耗多少空间？
构造一个网格图，让 DFS 的递归深度尽量大。如果起点是 $(0, 0)$ 要如何构造？如果起点是 $(i, j)$ 要如何构造？

欢迎在评论区发表你的思路。

算法题单

如何科学刷题？

如果你发现有题目可以补充进来，欢迎评论反馈。

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

一、网格图 DFS ​

二、网格图 BFS ​

三、网格图 0-1 BFS ​

四、网格图 Dijkstra ​

五、综合应用 ​

思考题 ​