第五课的方向数组dx/dy和地图模拟课上听着很简单无非就是两个数组加一个循环。但真正落到课后习题上很多同学会卡在莫名其妙的 bug 上要么数组越界程序崩溃要么走进死循环出不来要么输出结果和题面要求的正好反着。这篇内容我就把这套课后习题完整拆开讲每一道题都会说清楚思路、代码和易踩的坑顺带把方向数组这个工具的真正用法讲透。如果你刚学完这一课或者正被地图类模拟题折磨这篇可以直接对照着练。1. 方向数组的本质为什么一行循环能代替四个 if1.1 dx/dy 到底在做什么方向数组的经典写法是这样的int dx[4] {0, 0, 1, -1}; // 行的变化不动、不动、下移、上移 int dy[4] {1, -1, 0, 0}; // 列的变化右移、左移、不动、不动这里的坐标约定是(x, y)其中x表示行索引y表示列索引。很多新手第一次看到这组数组会懵为什么不是(x, y)分别代表横纵坐标这就牵扯到一个关键问题在 C 的二维数组或字符串数组表示的地图里第一维永远是行第二维永远是列。所以dx管的是上下移动dy管的是左右移动不要被数学课上习惯的“x 轴左右、y 轴上下”带偏了。dx[4]和dy[4]是一一对应的关系。dx[i]和dy[i]合起来描述一个方向的移动量。比如i0时(dx[0], dy[0]) (0, 1)表示行不变、列加一也就是向右移动一格i1时表示向左i2时表示向下i3时表示向上。四个下标就对应了四个方向。1.2 为什么要用数组而不是直接写四个 if这是这一课最该想明白的问题。如果不用方向数组想遍历当前格子(x, y)的上下左右四个邻居代码会写成这样if (x 1 n) { /* 处理下方格子 */ } if (x - 1 0) { /* 处理上方格子 */ } if (y 1 m) { /* 处理右方格子 */ } if (y - 1 0) { /* 处理左方格子 */ }四个 if 看起来也能解决问题但问题在于一旦方向变成八个加上四个斜角或者骑士跳法的八个方向if 版本会把代码撑得非常臃肿而且每个分支里要处理的逻辑完全重复。方向数组的价值在于把“枚举邻居”这件事变成一次统一的循环for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 后续逻辑统一处理 }这样就建立了“方向-循环-索引”的对应关系代码可读性高也方便扩展成八方向比如int dx8[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[8] {-1, 0, 1, -1, 1, -1, 0, 1};这种循环结构在后面的 DFS、BFS、路径模拟、连通块统计里会反复出现是地图模拟类问题的基本功。1.3 方向数组在地图模拟里的典型场景地图模拟的核心动作就是“从一个格子走到另一个格子”而方向数组就是描述“怎么走”的标准语言。常见场景包括判断当前格子周边的情况比如扫雷、地形统计、遍历地图上的连通区域比如岛屿数量、模拟移动规则比如机器人沿墙走、蛇形走位、按特定顺序访问地图比如螺旋矩阵。这些场景的共同点是每一次移动都遵循同一套偏移规则。只要把偏移规则集中到 dx/dy 里剩下的事情就是循环 边界判断 状态标记。想通这一点地图模拟题就成功了一半。2. 地图模拟的通用套路存图、越界检查与方向约定2.1 地图怎么存地图模拟题里最常见的输入是一个矩形区域字符或数字构成行和列之间没有空格。遇到这种格式我建议直接用vectorstring存代码短调试的时候打印也方便int n, m; cin n m; vectorstring mp(n); for (int i 0; i n; i) { cin mp[i]; // 一行一个字符串刚好是这一行的地图 }访问第tx行第ty列的字符就是mp[tx][ty]。如果地图里需要记录额外状态比如某个格子是否被访问过再加一个vectorvectorint vis(n, vectorint(m, 0));这个二维数组的索引规则和地图完全一致。2.2 越界检查的标准模板这是一套可以直接“抄作业”的模板。在 C 里字符串数组的合法下标范围是0 ~ n-1行、0 ~ m-1列。每次计算完新坐标(nx, ny)之后第一件事就是判断是否越界越界就跳过其他逻辑一概不管。判断函数建议直接写成内联或 lambdaauto ok [](int x, int y) - bool { return x 0 x n y 0 y m; };然后在循环里统一使用for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (!ok(nx, ny)) continue; // 此时可以安全访问 mp[nx][ny] }这里有一个很重要的细节continue一定要放在访问地图之前。新手最容易犯的错就是在循环里访问mp[nx][ny]之后才想起判断边界结果程序运行到地图边缘直接越界崩溃。养成“先判断再访问”的习惯这类问题基本能避免大半。2.3 方向顺序怎么约定方向数组的四个方向顺序不是固定的用{上, 右, 下, 左}或者{右, 下, 左, 上}都可以但同一个程序里要保持一致。我的建议是除非题目明确要求按顺时针或逆时针搜索否则就把常用顺序固定下来。比如迷宫类题目常按“上、右、下、左”即dx[4] {-1, 0, 1, 0}; dy[4] {0, 1, 0, -1};搜索因为局部优先向上和向右在某些题里会让期望路径更直观。但是要注意一旦用了某个顺序就必须保证所有地方都用同一个顺序。如果你在 DFS 里用“上右下左”在 BFS 里改成“右下左上”两个方向数组的dx、dy写混最终结果很可能和你预想的完全相反而且这种 bug 特别难排查因为它不崩溃只是结果不对。3. 课后习题逐题拆解从简单到复杂3.1 习题一统计相邻空地数量方向数组初体验题目描述给定一个n行m列的地图. 表示空地# 表示障碍物。对于地图上的每一个 #统计它上下左右四个方向相邻的空地数量按顺序输出每个 # 的统计值。这道题放在第一道目的是让你先学会“用方向数组看邻居”。思路很直白遍历全图遇到#就开一个计数器用方向数组循环四个方向判断每个方向上的新坐标(nx, ny)是不是合法合法再看对应格子是不是.。参考代码#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorstring mp(n); for (int i 0; i n; i) cin mp[i]; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; auto ok [](int x, int y) - bool { return x 0 x n y 0 y m; }; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] #) { int cnt 0; for (int k 0; k 4; k) { int nx i dx[k]; int ny j dy[k]; if (ok(nx, ny) mp[nx][ny] .) { cnt; } } cout ( i , j ) - cnt endl; } } } return 0; }这道题最容易出错的点是ok(nx, ny)判断之后又写了一个mp[nx][ny] .的条件两个条件同时成立才计数。有些同学会把ok写反比如写成nx 0 nx m行和列的边界值搞混一旦地图不是正方形就会出错。记住nx对应行范围是nny对应列范围是m这个对应关系不能乱。3.2 习题二岛屿数量连通块与 DFS题目描述给定一个n行m列的地图1表示陆地0表示水陆地与上下左右相邻的陆地连接成一个岛屿统计地图中有多少个岛屿。岛屿数量是方向数组最经典的应用本质是统计连通块个数。思路遍历地图遇到一个未访问过的1就把岛屿数量加一然后从这个格子出发用 DFS 或 BFS 把所有相邻的1全部标记为已访问。标记过的陆地后面再遇到就跳过这样每个岛屿只会被计数一次。参考代码DFS 递归版#include bits/stdc.h using namespace std; int n, m; vectorstring mp; vectorvectorint vis; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; void dfs(int x, int y) { vis[x][y] 1; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx n ny 0 ny m !vis[nx][ny] mp[nx][ny] 1) { dfs(nx, ny); } } } int main() { cin n m; mp.resize(n); vis.assign(n, vectorint(m, 0)); for (int i 0; i n; i) cin mp[i]; int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] 1 !vis[i][j]) { ans; dfs(i, j); } } } cout ans endl; return 0; }这道题我要重点强调一个细节vis[x][y] 1;必须放在 DFS 函数进入时的第一行不能等访问邻居时才标记。否则在极端情况下比如整张地图全是陆地递归调用会反复回到同一个格子最后栈溢出崩溃。另外如果地图很大比如 1000×1000 全陆地递归版 DFS 的调用深度可能达到百万层很容易爆栈。这时候建议改成 BFS 或者维护一个显式栈的 DFS。课后题里如果数据范围没有说明我会默认你用的是 BFS 版本因为它更稳。BFS 写法也不复杂queuepairint, int q; q.push({i, j}); vis[i][j] 1; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx n ny 0 ny m !vis[nx][ny] mp[nx][ny] 1) { vis[nx][ny] 1; q.push({nx, ny}); } } }注意 BFS 里标记访问的时机应该在入队时标记而不是出队时标记。如果出队时才标记同一个格子可能被多个邻居重复入队队列里会堆积大量重复元素在大地图上既慢又容易出错。3.3 习题三机器人扫地方向转换与路径模拟题目描述一个房间用n行m列的网格表示有一个机器人从(0, 0)出发初始朝右。机器人按以下规则移动如果前方格子还在房间内且没有走过就往前走一步否则顺时针转 90 度继续尝试。请按访问顺序输出机器人走过的路径坐标。这是方向数组在地图模拟上的进阶应用重点考察“转向”这个动作。核心思路用变量dir记录当前方向在 dx/dy 数组中的下标dir的取值范围是0 ~ 3。每次尝试前进时先算nx x dx[dir]; ny y dy[dir];然后判断这个位置是否越界或已访问如果可以走就走不能走就dir (dir 1) % 4;转向后再试。参考代码#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorvectorint vis(n, vectorint(m, 0)); int dx[4] {0, 1, 0, -1}; // 右、下、左、上顺时针 int dy[4] {1, 0, -1, 0}; int x 0, y 0, dir 0; vis[x][y] 1; cout ( x , y ); int total n * m; for (int step 1; step total; step) { int nx x dx[dir]; int ny y dy[dir]; if (nx 0 || nx n || ny 0 || ny m || vis[nx][ny]) { dir (dir 1) % 4; nx x dx[dir]; ny y dy[dir]; } x nx; y ny; vis[x][y] 1; cout - ( x , y ); } cout endl; return 0; }这里有个非常关键的细节转向后要重新计算nx和ny。很多同学写完第一次判断发现不能走直接改dir然后继续用旧的nx、ny结果机器人原地不动或者穿墙。正确的做法是在dir变化之后立刻基于新的dir重新计算一次目标坐标。还有一个容易忽略的点这个循环为什么用for (int step 1; step total; step)而不是while因为我们已经知道机器人一共会走n * m个格子用while的话很容易陷入死循环而不自知。用步数控制循环理论上走完所有格子就一定结束也方便判断逻辑是否正确。我见过很多同学在这道题里写成这样while (true) { if (越界或已访问) dir (dir 1) % 4; x dx[dir]; y dy[dir]; }一旦所有方向都走不通理论上不可能但代码里可能出现这个while (true)就会死循环。用步数控制的for循环可以从源头上避免这个问题。3.4 习题四螺旋矩阵原地转向与已访问标记的配合题目描述给定一个n行m列的矩阵按顺时针螺旋顺序输出每个元素。要求从(0, 0)开始方向依次为右、下、左、上遇到边界或已经访问过的格子就顺时针转向。螺旋矩阵本质上就是机器人扫地题的输出变体区别在于机器人扫地需要记录顺序螺旋矩阵直接输出元素值。解题思路和上一题几乎一样用vis记录已访问位置每次计算下一步如果出界或已访问就转向。但这里有一个优化空间可以用四个边界变量top, bottom, left, right来标记未访问的边界范围不需要vis数组。用方向数组版的做法更直观#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorvectorint a(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } vectorvectorint vis(n, vectorint(m, 0)); int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; int x 0, y 0, dir 0; vectorint ans; ans.push_back(a[0][0]); vis[0][0] 1; while (ans.size() n * m) { int nx x dx[dir]; int ny y dy[dir]; if (nx 0 || nx n || ny 0 || ny m || vis[nx][ny]) { dir (dir 1) % 4; continue; } x nx; y ny; vis[x][y] 1; ans.push_back(a[x][y]); } for (int i 0; i ans.size(); i) { cout ans[i] (i 1 ans.size() ? \n : ); } return 0; }这道题我用while (ans.size() n * m)作循环条件因为循环次数不确定但结束条件是明确的所有格子都已访问。这里还有一个技巧转向后continue重新进入循环重新计算nx和ny这样写比在转向后直接赋值更清晰减少了重复代码。需要注意dir (dir 1) % 4;可以连续转向。比如螺旋矩阵转到左下角时需要从“向左”连续转两次变成“向上”这时第一次转向后nx, ny仍然不合法再次进入if再次转向直到方向合法。这个逻辑放在while循环里是自动成立的但如果写成if而不是while就只能转一次方向程序就卡住了。3.5 习题五扫雷空白展开八方向的实战题目描述模拟扫雷游戏的空白区域展开。给定一个n行m列的雷区地图*表示地雷数字0~8表示该格子周围的地雷数量。玩家点击一个坐标为0的格子所有与它相邻的0格子以及这些0格子周围的数字格子都会被自动翻开。请输出点击后地图上所有被翻开的格子坐标。这道题是方向数组从四方向扩展到八方向的典型练习。为什么扫雷要用八方向因为经典扫雷规则里一个格子周围的地雷数量是九宫格范围内统计的包含斜对角。所以这里的方向数组要换成int dx8[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[8] {-1, 0, 1, -1, 1, -1, 0, 1};解题思路从点击的格子开始 BFS。如果是0格子就把它的八方向邻居全部入队如果是数字格子只翻它本身不继续扩散。注意访问标记仍然需要否则会反复入队。参考代码BFS 版#include bits/stdc.h using namespace std; int main() { int n, m, sx, sy; cin n m sx sy; vectorstring mp(n); for (int i 0; i n; i) cin mp[i]; int dx8[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[8] {-1, 0, 1, -1, 1, -1, 0, 1}; vectorvectorint vis(n, vectorint(m, 0)); queuepairint, int q; q.push({sx, sy}); vis[sx][sy] 1; while (!q.empty()) { auto [x, y] q.front(); q.pop(); cout 翻开 ( x , y )\n; if (mp[x][y] ! 0) continue; // 数字格子不扩散 for (int i 0; i 8; i) { int nx x dx8[i]; int ny y dy8[i]; if (nx 0 nx n ny 0 ny m !vis[nx][ny]) { vis[nx][ny] 1; q.push({nx, ny}); } } } return 0; }这道题一定要留意入队条件vis[nx][ny] 1;要和q.push({nx, ny});成对出现而且是在入队时标记不是取出时。原因前面说过不立即标记会导致同一格子被多个邻居重复加入队列扫雷这种八方向扩散场景下队列会爆炸。4. 新手最容易踩的坑与排查技巧4.1 越界越界还是越界地图模拟题里最经典的运行错误就是数组越界。现象是程序崩溃报错segmentation fault或者std::out_of_range。原因几乎都是访问mp[nx][ny]前没有判断nx和ny是否合法。排查方法如果程序在小规模测试数据上正常但换了大一点的数据就崩优先检查所有mp[nx][ny]访问点确认它们前面都有越界判断。也可以把ok函数抽出来统一调用不要在每个循环里各写各的判断逻辑避免漏判。4.2 死循环与全图标记死循环在高频出现在 DFS/BFS 或机器人模拟题里。最常见原因是访问标记写错位置或漏写。比如 BFS 里用vis标记但标记放在了pop之后而不是push时同一格子可能被多个方向重复加入队列无限增长程序卡死甚至内存耗尽。另一个死循环场景是机器人模拟转向后没有重新计算坐标导致机器人原地打转。排查时可以在循环里打印当前坐标和方向打印几轮就能看出问题在哪。4.3 方向搞反上下左右方向反了的结果不是崩溃而是答案错误。常见原因dx和dy的顺序写反了或者在nx x dx[k]里把dy的值当成了行偏移。排查技巧专门写一个 3×3 的地图把当前格子标记出来然后打印四个邻居的实际坐标对照手算结果很快就能发现方向问题。养成这个验证习惯后面做任何地图题都能少走弯路。4.4 输入问题带空格的数字地图用cin a[i][j]没问题但字符地图里如果行与行之间有空行cin string会跳过空白符直接读取通常没问题。容易出错的是输入完之后缓冲区残留换行符导致下一个字符串读进空内容。如果遇到读入错位的情况检查是不是在cin n m;之后用了getline。我的建议是字符地图一律用cin mp[i]避免混用getline。4.5 调试小技巧地图模拟类题目最好的调试方式就是把地图状态打出来看。写一个打印函数void printVis(vectorvectorint vis, int n, int m) { for (int i 0; i n; i) { for (int j 0; j m; j) { cout vis[i][j] ; } cout \n; } }在 BFS/DFS 的每一步调用它观察访问标记的扩散过程基本一眼就能看出是哪一步走错了。4.6 问题速查表现象可能原因解决办法程序崩溃段错误越界访问mp[nx][ny]所有访问前加边界判断程序运行很久不结束BFS/DFS 标记时机不对入队/入栈时立刻标记已访问输出结果方向反了dx、dy写混或者顺序不一致用 3×3 小图验证方向数组机器人不走/原地打转转向后没重新计算坐标转向后用continue重新判断读入的地图行错位getline混用字符地图统一用cin string第五课这套方向数组课后题说到底是同一个工具的反复演练。四方向、八方向、转向模拟、连通块统计骨架都是那两行数组和一层循环差别只在边界条件和状态维护上。我建议你学完以后不要急着做更难的内容先把每一道题的手算过程走一遍再对照代码跑一遍最后尝试把八方向扩展成十六方向或者把某个题从 BFS 改成 DFS。方向数组一旦用顺手后面学图论遍历、迷宫寻路、游戏开发里的格子移动逻辑都会顺畅很多。
