迷宫与地图模拟完整体验方向数组 dx/dy 的进阶练法如果你上过几次算法课大概已经被“方向数组”这个词听过不下十遍了。它简单到不行——就是用int dx[4] {-1, 1, 0, 0};配合int dy[4] {0, 0, -1, 1};表示上下左右四个方向再配合循环来访问地图里的相邻格子。但实话实说我在带新人的时候发现大部分同学看完课都会说“哦我会了”真到做题的时候十个里有七八个会栽在方向序、边界判断、回溯状态复位这些细节上。这堂课的课后习题就是专门针对这个问题的。下面我从头到尾梳理一遍方向数组的原理、地图模拟的套路以及五道核心习题的完整解法帮你把这块基础彻底压实。1. 先想清楚为什么是 dx / dy而不是 if else 四连1.1 从“四个 if”到“一个循环”的思维转变先看一个最常见的场景给一个网格地图起点在(x, y)要依次访问上下左右四个邻居格子。最直观、也是零基础选手最常写的写法是这样的// 上(x-1, y) if (x - 1 0 x - 1 n) { visit(x - 1, y); } // 下(x1, y) if (x 1 0 x 1 n) { visit(x 1, y); } // 左(x, y-1) if (y - 1 0 y - 1 m) { visit(x, y - 1); } // 右(x, y1) if (y 1 0 y 1 m) { visit(x, y 1); }这样写有没有问题逻辑上完全没问题新手能写成这样已经算清楚边界了。但问题在于代码里充满了重复逻辑而且一旦方向增加到8个加上斜对角、或者遍历规则要动态调整比如蛇形、螺旋这种写法就非常难改。方向数组把“方向”本身变成了数据int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 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) continue; visit(nx, ny); }一次循环四个方向全部覆盖边界检查集中处理逻辑清晰可维护性高出一个数量级。这就是方向数组的核心价值把重复的结构化逻辑抽象为数据用循环统一驱动。1.2 方向序有讲究顺时针还是逆时针方向数组的排列顺序不是随便写的。虽然大多数题目对访问顺序不敏感但有一类题特别在意求旋转矩阵、螺旋遍历、判断方向变化的题目。顺时针序是最常用的写法是(-1, 0) 上(0, 1) 右(1, 0) 下(0, -1) 左对应数组int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};这样排的好处是如果要实现“撞墙右转”的逻辑只需要dir (dir 1) % 4;就能让方向按顺时针轮转。如果方向是乱序排的轮转逻辑就会变成一团乱麻。注意很多教材会先把dx放在前面讲“上、下、左、右”也就是{-1, 1, 0, 0}配{0, 0, -1, 1}。这种排法在普通遍历中没问题但如果题目涉及方向切换建议一律改成“上右下左”的顺时针序后续写螺旋矩阵、贪吃蛇都不用重新调。1.3 如果方向变成8个呢斜向移动在地图题里也常见比如“王的走法”“棋盘马走日”。8方向数组同样简单int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};这个顺序是从左上角开始按行扫描覆盖了3x3区域的所有邻居不包括自身。8方向的遍历套路和4方向完全一致只是循环从4次变成8次边界判断逻辑不变。你只要理解一次后面全是一样的写法。2. 地图模拟的关键前提初始化、边界与访问标记2.1 地图数组与坐标系的统一在做地图模拟之前脑子里一定要有一张清晰的“坐标系图”。在C里二维数组a[n][m]的a[x][y]中x是行号从0到n-1向下增大y是列号从0到m-1向右增大。这和数学里常见的直角坐标系不同x不是横轴而是纵轴。所以方向数组里dx -1表示行号减小也就是向上走dy 1表示列号增大也就是向右走。这一点看似基础但我在实际教学里见过太多人把dx和dy混用导致角色斜着走、或者完全走反方向。建议第一次敲代码前先在注释里把坐标系画出来// (-1, 0) // (0,-1) (x,y) (0,1) // (1, 0)2.2 越界检查别把号漏了方向数组最常见的翻车现场就是越界判断少了个等号。比如地图尺寸是n 5行下标范围是0~4合法判断必须写成if (nx 0 || nx n || ny 0 || ny m) continue;注意 n而不是 n因为数组最后一个合法下标是n - 1。等号漏掉的话程序会访问a[5]或a[n][...]这是未定义行为轻则读到脏数据重则直接Segment Fault崩溃。这个错误在OJ上通常报Runtime Error不少新手看到三个字母就懵了完全想不到是自己边界写错。2.3 访问标记走过的地方要“记账”地图模拟题十有八九需要防止重复访问。常见的标记方式有这么几种布尔标记数组bool vis[n][m] {};初始全部为false访问过就置true。原地修改地图把走过的格子改成特殊值比如grid[nx][ny] #;。步数记录需要在BFS里记录层数时直接用一个dist[n][m]数组初始为-1起点设0之后每次扩展时dist[nx][ny] dist[x][y] 1。这样“有没有访问过”和“走了多少步”两个信息合一了效率最高。这三种方式各有用处纯 DFS 遍历用布尔数组最直观迷宫类题用dist数组一步到位而像“统计岛屿数量”这类需要修改地图的题原地改0可以省一个数组的空间。3. 课后习题逐题拆解从 BFS 到方向切换模拟3.1 习题一迷宫最短路BFS 经典题题目描述给定一个n x m的迷宫.表示可走#表示墙。起点在(0,0)终点在(n-1,m-1)只能上下左右走求最短路径长度。如果不可达输出-1。思路分析迷宫求最短路径第一反应必须是 BFS。按“由近到远”逐层扩展第一次到达终点时的步数一定是最短步数。方向数组在这里负责生成每一步的四个候选位置。完整代码#include bits/stdc.h using namespace std; const int MAXN 105; char maze[MAXN][MAXN]; int dist[MAXN][MAXN]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int main() { int n, m; cin n m; for (int i 0; i n; i) { cin maze[i]; } memset(dist, -1, sizeof(dist)); queuepairint,int q; q.push({0, 0}); dist[0][0] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); // 提前判断如果到达终点直接输出并退出 if (x n - 1 y m - 1) { cout dist[x][y] endl; return 0; } 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) continue; if (maze[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } cout -1 endl; return 0; }踩过的坑忘记初始化dist数组。memset(dist, -1, sizeof(dist))只对int数组的-1有效因为-1在所有字节位都是0xFF。如果你用0初始化再判断“是否访问过”那就没法区分“没访问”和“走了0步”。这就是我用-1初始化的原因。坐标写反pairint,int里第一个是x行第二个是y列。有人说“反正我用firstsecond不就行了”但一旦x和y混了改起来就是灾难。所以我在读入时直接从cin读字符矩阵i就是行号j就是列号一一对应。终点处理放在出队时判断是对的但也有人会在入队时就判断结果到终点前一步就提前返回了少算一步。建议只在出队时判断。复杂度每个格子最多入队一次时间复杂度O(n*m)空间复杂度O(n*m)。3.2 习题二统计岛屿数量DFS 去重题目描述给出一个n x m的01矩阵1代表陆地0代表水。相邻上下左右的1属于同一个岛屿求岛屿总数。思路分析遍历整个地图遇到1就把计数器加一然后从该点出发用 DFS 把所有相邻的1都改成0相当于“淹掉”这个岛。这样后面遍历时不会重复计数。完整代码#include bits/stdc.h using namespace std; const int MAXN 505; int grid[MAXN][MAXN]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int n, m; void dfs(int x, int y) { grid[x][y] 0; // 标记已访问直接淹掉 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) continue; if (grid[nx][ny] 1) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) { ans; dfs(i, j); } } } cout ans endl; return 0; }为什么 DFS 也能用在这里我们只需要知道岛屿数量不需要知道最短路径所以不需要层级概念DFS 天然合适。而且直接用原地改值的方式做标记省掉了vis数组内存优势明显。一个容易忽视的点grid[x][y] 0;必须放在 DFS 函数的最开头而不是在循环里面调用之后才标记。如果你只在调用dfs(nx, ny)之前标记对于已经入栈但还没执行到的点可能出现重复入栈严重的会栈溢出。3.3 习题三蛇形填数方向切换模拟题目描述输入n输出一个n x n的方阵从左上角开始按“右→下→左→上→右→下…”的顺序依次填入1, 2, 3, ..., n*n。这个方向在撞到边界或已填过的格子时就顺时针转 90 度。这个题在网上有无数种叫法有的叫蛇形填数有的叫螺旋矩阵本质上就是同一个东西。思路分析这道题是方向数组“方向切换”场景的入门必做题。核心逻辑是每次沿当前方向走如果下一步越界或者目标格子已经填过数就换个方向继续走。完整代码#include bits/stdc.h using namespace std; int a[20][20]; int main() { int n; cin n; // 顺时针方向右、下、左、上 int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; int x 0, y 0, dir 0; for (int i 1; i n * n; i) { a[x][y] i; int nx x dx[dir]; int ny y dy[dir]; if (nx 0 || nx n || ny 0 || ny n || a[nx][ny] ! 0) { dir (dir 1) % 4; // 转方向 nx x dx[dir]; ny y dy[dir]; } x nx; y ny; } for (int i 0; i n; i) { for (int j 0; j n; j) { cout setw(4) a[i][j]; } cout endl; } return 0; }这个解法里最关键的设计是dir (dir 1) % 4这一行。它保证方向永远在“右→下→左→上”之间循环。由于dir对 4 取模所以超过 3 之后自然回到 0形成一个闭合环路。为什么要用a[nx][ny] ! 0作为“已填过”的判断标准因为数组默认初始化为 0而填入的数字从 1 开始。如果某个位置已经填过它一定大于 0不可能等于 0。这样省掉一个额外的标记数组。3.4 习题四简化贪吃蛇位置模拟题目描述在一个10 x 10的空棋盘上蛇初始位置在(0,0)长度为 3身体依次是(0,0)、(0,1)、(0,2)头朝右。每一步玩家输入一个字符W上、S下、A左、D右蛇头按输入方向移动一步。移动后蛇尾同时向前缩进保持长度 3 不变。如果蛇头撞到边界输出Game Over并结束如果蛇头移动到了身体上同样输出Game Over。否则输出当前蛇头坐标。思路分析这个题本质就是“队列模拟 方向数组”。蛇身可以用一个队列来维护队头是蛇尾队尾是蛇头或者反过来看你习惯。每次移动时弹出蛇尾长度保持不变新的蛇头按方向数组计算出来。检查是否撞墙、是否撞身确定游戏是否继续。完整代码#include bits/stdc.h using namespace std; struct Point { int x, y; }; bool body[15][15]; dequePoint snake; int main() { mapchar, int dirMap; dirMap[W] 0; dirMap[S] 1; dirMap[A] 2; dirMap[D] 3; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; // 初始化蛇尾部在(0,0)头部在(0,2)长度为3 for (int i 0; i 3; i) { snake.push_back({0, i}); body[0][i] true; } int n; cin n; // 操作次数 while (n--) { char op; cin op; int dir dirMap[op]; auto head snake.back(); int nx head.x dx[dir]; int ny head.y dy[dir]; // 撞墙判断 if (nx 0 || nx 10 || ny 0 || ny 10) { cout Game Over endl; return 0; } // 撞身判断注意如果新位置恰好是蛇尾即将离开的位置不算撞 auto tail snake.front(); if (body[nx][ny] !(nx tail.x ny tail.y)) { cout Game Over endl; return 0; } // 移动删除旧蛇尾增加新蛇头 // 注意要先删尾部再判断新头部是否会撞到即将离开的尾部 body[tail.x][tail.y] false; snake.pop_front(); snake.push_back({nx, ny}); body[nx][ny] true; cout nx ny endl; } return 0; }这道题特别容易踩的一个坑撞身判断的顺序。假如蛇正向右移动蛇头的新位置恰好是蛇尾当前所在的位置这算不算撞身严格来说不算因为蛇尾在移动的同一时刻会腾出位置。所以要先“拿到尾巴坐标但不删除”判断完再删或者在入队前判断时排除尾巴坐标。还有一个坑是方向映射的写法。直接用mapchar, int固然看得懂但在竞赛里有人为了省事写成四个if判断也是可以的。个人建议用数组下标映射dir[op]但需要把字符转成对应的0~3这个看个人习惯逻辑上都没问题。3.5 习题五连通块染色方向数组 递归回溯题目描述给定一个n x m的矩阵每个格子有颜色编号0~9。所有颜色相同的相邻格子属于同一个连通块。请给每个连通块编号并输出染色后的矩阵。编号从 1 开始。思路分析这个题和“统计岛屿数量”本质相同但多了一步“涂色”。我们可以用 DFS 遍历每个连通块同时维护一个colorId把访问过的格子涂成colorId 0或者用单独的ans数组保存染色编号。代码示例核心部分#include bits/stdc.h using namespace std; int n, m; int grid[105][105]; int ans[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y, int color, int id) { ans[x][y] id; 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) continue; if (ans[nx][ny] ! 0) continue; // 已经染色 if (grid[nx][ny] ! color) continue; // 不同颜色 dfs(nx, ny, color, id); } } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; int id 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (ans[i][j] 0) { id; dfs(i, j, grid[i][j], id); } } } for (int i 0; i n; i) { for (int j 0; j m; j) cout setw(3) ans[i][j]; cout endl; } return 0; }DFS 递归在这里会自动处理回溯因为我们要的是“填满整个连通块”不需要把标记撤销。如果你误加了ans[nx][ny] 0的撤销语句反而会导致同一个点被重复访问形成死循环。这个点很值得注意遍历类 DFS 不回溯路径类 DFS 才回溯。4. 排查地图模拟题的通用方法论4.1 万能调试法打印地图新手最容易犯的毛病就是代码写完了直接提交错了再对着代码干瞪眼。更有效的做法是先把中间过程打印出来看看。尤其是地图模拟题“打印地图”几乎能解决 80% 的调试问题。比如蛇形填数题你可以每填完一行就打印一次矩阵肉眼看看有没有跳到错误位置for (int i 0; i n; i) { for (int j 0; j n; j) cout setw(4) a[i][j]; cout endl; }在调试阶段把这段临时打印代码放在循环里观察每一圈的变化。确认无误后再删除正式输出。4.2 边界用例自查清单每次写完地图题都建议自己先跑一遍这些边界用例1x1的单格子地图。很多代码在1x1时会出现问题比如 BFS 里起点就是终点的情况。1行多列或1列多行的长条形地图。它专门测试方向数组里dx和dy的对称性是否写反。全墙地图全#确保能输出-1而不是死循环。全空地地图检查遍历性能是否正常。4.3 死循环是怎么产生的地图题的死循环通产来自三个原因没有访问标记或者标记位置不对。这是大头。方向数组旋转写反了方向序比如蛇形填数方向切到错误方向。递归 DFS 中未正确判断边界导致递归越来越深直到爆栈。排查思路很简单加一个计数器限制循环次数。或者在 DFS 入口打印当前坐标观察(x, y)是否在几个格子之间反复横跳。如果是多半是标记未生效或者是撞身判断写反了。5. 进阶方向从二维地图到更复杂的模拟方向数组的应用远不止这五道题。在二维地图题里它是最底层的地基。下面列几个进阶方向等这节课的内容吃透后可以往这几个方向继续延伸网格 DFS 求连通块数量/面积/周长一句话总结就是“遍历所有点碰到未访问的陆地就 DFS 旱地拔葱”。多源 BFS假设有多个起点比如多个火源同时蔓延求每个格子被烧到的最短时间。做法是把所有起点全部入队再统一 BFS方向数组照用。带权重的方向选择比如每个方向的移动代价不一样配合 Dijkstra 算法使用。这时方向数组依然负责生成邻居但出队逻辑要从普通队列换成优先队列。三维方向数组比如立体迷宫、六面体展开问题。把dx/dy扩展为dx/dy/dz即可循环从 4 次变 6 次原理不变。不知道你有没有发现方向数组的“威力”不是它本身有多厉害而是它把“位置变化”这件事从条件判断里解放出来了。无论是 BFS 的队列扩展、DFS 的递归深入还是贪吃蛇的方向切换、螺旋矩阵的转向底层逻辑都是一样的给定当前坐标通过方向数组生成下一个坐标检查合法性后再决定是否移动。6. 练完这些题你的真实水平应该在哪个档位按照我的经验一个学生如果能独立把上面五题全部做对不看题解、不抄代码那他在“二维地图遍历”这个板块就已经超过 90% 的初级选手了。这些题覆盖了方向数组的基础使用BFS/DFS 遍历方向切换与轮转蛇形填数状态维护与碰撞检测贪吃蛇坐标变换与地图染色连通块接下来可以挑战的题目方向是 OpenJudge 或力扣上的“岛屿数量”“腐烂的橘子”“迷宫最短路径”等题型它们都是这些课后题的变种。最后再说一个小技巧在写任何地图模拟题的时候我都建议在代码文件的最开头写好dx/dy的注释标明方向对应关系。这不只是为了给别人看更是防止自己写到后面突然忘记顺序。方向顺序错了很多题你看半天代码都找不出问题因为代码逻辑“看起来没问题”。用注释把方向定死出问题的时候第一件事就是核对dx/dy数组我一直觉得这个习惯帮我节省了非常多不必要的 debug 时间。课后题的练习建议不要只跑题目给的样例还要自己多构造几个特殊的输入比如超小地图、细长条地图、全障碍地图。调通了这些情况你的方向数组才算真正过关。