网格图搜索 · 考级冲刺

很多搜索题的舞台是一张网格（迷宫、地图、棋盘）：数有几块连通区域、求从起点到终点的最短路、求某个连通块最大有多大——都是在网格上跑 DFS 或 BFS。网格搜索有个标配写法：方向数组。

上下左右四个方向的坐标偏移：

int dx[] = {-1, 1, 0, 0};    // 上、下
int dy[] = {0, 0, -1, 1};    // 左、右
// 从 (x, y) 走到四个邻居：
for (int k = 0; k < 4; k++) {
    int nx = x + dx[k], ny = y + dy[k];
    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 越界
    if (vis[nx][ny] || grid[nx][ny] == '#') continue;      // 访问过 or 障碍
    // 走到 (nx, ny)
}

有了方向数组，四个方向用一个循环搞定，不用把上下左右各写一遍，既短又不易漏。如果题目允许斜着走，就把数组扩成 8 个方向。

坑：每走一步都要先判越界、再判障碍和是否访问过，顺序别反（先判越界能防止数组下标溢出）。数连通块用 DFS/BFS 把一整块染色，求最短路用 BFS。整张 $n \times m$ 的网格每个格子只访问一次，复杂度是 $O (nm)$ 。