矩阵与网格算法：二维数组里的图搜索与 DP

这部分知识我前后看过不止一次。刚接触“矩阵与网格算法：二维数组里的图搜索与 DP”时，二维网格看起来只是数组多了一维，但我写搜索时经常重复访问、越界，甚至分不清它什么时候其实是一张图。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

矩阵和网格题经常出现在搜索、动态规划和图论中。它们表面是二维数组，本质上每个格子都可以看作图中的一个节点，上下左右或八个方向就是边。

把矩阵看成图

图：矩阵里的相邻格子就是图里的边

矩阵题常见类型：

类型	思路
岛屿数量	DFS/BFS 标记连通块
腐烂橘子	多源 BFS
最短路径	BFS 或 Dijkstra
不同路径	动态规划
单词搜索	DFS + 回溯
旋转矩阵	原地交换

方向数组

方向数组可以让代码更统一。

int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

遍历邻居时：

for (int[] d : dirs) {
    int nr = r + d[0];
    int nc = c + d[1];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
    // 处理合法邻居
}

岛屿数量

int numIslands(char[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int ans = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                ans++;
                dfs(grid, r, c);
            }
        }
    }
    return ans;
}

void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
    if (grid[r][c] != '1') return;
    grid[r][c] = '2';
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

这里直接修改原矩阵作为访问标记。如果不能修改输入，就额外使用 visited。

多源 BFS

有些题不是从一个起点扩散，而是多个起点同时扩散。例如腐烂橘子、离最近的 0 的距离。

int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            if (grid[r][c] == 1) fresh++;
        }
    }

    int minutes = 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty() && fresh > 0) {
        for (int size = queue.size(); size > 0; size--) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr][nc] != 1) continue;
                grid[nr][nc] = 2;
                fresh--;
                queue.offer(new int[]{nr, nc});
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

多源 BFS 的关键是把所有起点先放进队列，它们共同作为第 0 层。

矩阵 DP

如果每个位置的答案依赖左边、上边或前一行，通常可以用 DP。

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

如果只依赖上一行，可以压缩成一维数组。

我的分析

矩阵题最容易漏的是边界和访问状态。我的习惯是先写 rows、cols、dirs，再写 inBounds 判断。这样能减少复制粘贴导致的坐标错误。

如果题目问“最短几步”，我优先想 BFS；如果问“多少个连通块”，我优先想 DFS/BFS；如果问“路径数量或最优值”，我优先想 DP。

面试题

矩阵 DFS 什么时候可以直接修改原数组？
多源 BFS 和普通 BFS 有什么区别？
为什么无权网格最短路可以用 BFS？
矩阵 DP 如何判断遍历顺序？
八方向搜索和四方向搜索会改变什么？