咱们刷题、准备408的或者写过一段算法代码的朋友应该都被这类问题卡过走迷宫、扫雷、岛屿数量、单词搜索……看起来题目千变万化但解法掉进网格之后翻来覆去就是那几个操作——往上下左右挪一步判断出没出界再决定要不要接着递归或入队。这个“往哪挪一步”的动作就是图论里最不起眼却最不能错的基础设施之一方向数组。方向数组也叫方向增量数组、位移数组本质就是一组预先定义好的坐标偏移量。它可以被当成“网格建图”的桥梁也可以直接放进BFS/DFS的遍历框架里。很多新手能看懂深搜宽搜的概念一到手写代码就栽在方向数组上要么顺序写错要么边界判断漏了要么八方向的时候把斜对角和上下左右混在一起。这篇文章就把方向数组的定义、几种写法、配套的踩坑经验都捋一遍适合正在学数据结构与算法、准备考研复试、复习期末《数据结构》或者在刷题平台上卡在网格类题目的朋友。1. 方向数组的本质网格也是一张图1.1 为什么需要方向数组二维网格的“邻接表”很多人学图论的时候脑子里默认的图是邻接矩阵或者邻接表V个点E条边点与点之间靠链表或二维数组相连。可实际上有一大类图长得特别规整——矩阵、棋盘、迷宫、地图每个格子就是图里的顶点格子和格子之间是否相连取决于它们是否在物理位置上相邻。这种图不需要显式地存储“谁和谁相连”因为相邻关系是可以算出来的。一个格子(x, y)它的四个邻居无非就是(x1, y)、(x-1, y)、(x, y1)、(x, y-1)。你在写遍历的时候不需要手动敲四次 if 去判断四个方向只需要用一组“偏移量”在循环里统一加一遍就行。这组偏移量就是方向数组。我把方向数组理解成“二维邻接表的常量优化版”邻接表用动态内存存边方向数组用静态常量算边。图的正规性越强方向数组就越省事。它直接把“当前点能走到哪几个点”这个查询操作从 O(E) 变成了 O(1) 的常量查表代价只是牺牲一点点可读性——所以新手学的时候觉得它抽象其实它反而是最接近数学定义“平移变换”的东西。1.2 方向数组的内存本质增量组合方向数组的核心是“增量”。任意一次移动都可以拆成“行方向加多少”加上“列方向加多少”。如果我们规定行坐标增量存到dx[]里列坐标增量存到dy[]里那么从点(x, y)出发走第 k 个方向之后的新坐标就是nx x dx[k] ny y dy[k]四个基本方向的增量拆开看就是方向dx行偏移dy列偏移效果上-10行号减1列不变相当于往矩阵上方走下10行号加1列不变左0-1行不变列号减1右01行不变列号加1只要保证 dx 和 dy 按下标一一配对这四个方向无论怎么排列逻辑上都是一样的。把“上下左右”翻译成“行坐标增量为-1/1、列坐标增量为-1/1”其实就已经在拿图论的思维理解问题了。方向数组定义得对不对不是看顺序而是看配对关系是否完整覆盖了你需要的移动集合。1.3 四方向和八方向两种最常见的规格网格题最常见的移动方式有两种。第一种是四方向也就是普通上下左右走迷宫、岛屿面积这类题目通常只用四方向就够了。第二种是八方向在四方向基础上加上四个斜角用来解决类似“图像连通域”“骑士巡逻扩展”等问题。八方向的增量组合长这样dx {-1, -1, -1, 0, 0, 1, 1, 1} dy {-1, 0, 1,-1, 1,-1, 0, 1}如果你按“从左上角顺时针转一圈”来记顺序可以是(-1,-1) (-1,0) (-1,1) (0,1) (1,1) (1,0) (1,-1) (0,-1)这也是一种很常见的写法。八方向和四方向本质上就是同一个东西把增量组合从4个扩展到8个。唯一需要当心的是八方向里对角线移动的“距离”和上下左右移动的“距离”在几何上不一样斜边比直角边更长但在无权图的BFS/DFS里我们通常不区分这两者因为步数一律按1步算。这一点在具体题目里要看清题设有的题明确要求只能走十字方向那就别用八方向。2. 方向数组的三种定义方式从入门到进阶2.1 双数组法dx、dy分离最主流、最容易调试最普及的写法是开两个全局数组或者局部数组int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0};这种写法的好处是直观。遍历的时候一个循环搞定for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 判断边界、判断障碍、继续搜索 }过程中想调试某个方向的坐标直接打印dx[i]和dy[i]就能看到当前偏移量。想调整方向顺序也只需要改数组元素的位置不影响其他逻辑。这个方案是学习阶段最推荐的能避免很多低级错误。我见过一些人为了省事把 dx 和 dy 写成一个二维数组int dir[4][2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};从定义上讲完全没问题循环里改成x dir[i][0]、y dir[i][1]就行。可如果你不是刷题量很大的老手我建议还是用双数组因为dx[i]、dy[i]更容易读出来“哦现在是行方向变化还是列方向变化”而dir[i][0]这种写法稍一走神就分不清0和1谁是行谁是列。2.2 单数组法pair或struct适合复杂状态一起扩展如果状态不只是坐标还附带方向、步数、已访问的节点集合单靠 dx/dy 就略显单薄了。这时可以用结构体把状态打包struct State { int x, y; int dir; // 当前面向的方向 }; int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0};比如模拟“机器人扫地”“贪吃蛇移动”这类问题你的队列里真正需要的是“坐标方向”而方向数组负责生成“下一步的坐标和方向”。这种把方向索引也当成状态一部分的做法在方向数组应用中很关键方向数组不只是用来生成邻居还能用来表达“转向”。遇到那种“只能左转、右转、直行”的题目方向数组的顺序就变得重要了。你会把方向按下标排成上、右、下、左顺时针然后(dir 1) % 4就是右转(dir - 1 4) % 4就是左转。这时候方向数组升格成了“状态转移表”而不仅仅是一次性生成邻居的偏移量。2.3 特殊网格的预处理坐标编码配合查询有些地图不是标准矩形障碍物很多或者需要频繁查询“某个方向是否可走”。如果把方向数组跟坐标编码结合就能节省大量重复计算。一个常见技巧是把二维坐标压缩成一维用pos x * col y表示格子编号。方向数组依然定义成dx/dy但生成新位置的时候直接基于一维编码操作。配合一个障碍标记数组查询“这个方向上可不可以走”就变成了bool数组的一次索引。int encode(int x, int y, int col) { return x * col y; } int dirs[][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int pos encode(1, 2, m); int nx pos / m dirs[k][0]; int ny pos % m dirs[k][1];这种写法在双向BFS、A* 搜索里很常见因为把坐标编码成整数后可以用unordered_setint或者一维int[]直接做访问标记查找效率比setpairint,int高一大截。但要注意编码后的除法和取模有额外开销矩形网格还好稀疏网格可能不划算。3. 方向数组在BFS/DFS中的完整实操从建图到遍历3.1 边界判断是方向数组的“安全带”方向数组负责“生成新坐标”但新坐标未必合法。在网格搜索中最常见的非法情况就是越界——行号跑到-1或者列号等于m。所以每走一步都要先判断边界bool inArea(int x, int y, int n, int m) { return x 0 x n y 0 y m; }这里有个细节n 是行数m 是列数判断条件是x n、y m不是。因为下标从0开始第 n 行已经不存在了。新手写错这个的非常多特别是从 1-based 的题目转过来之后一不留神就写成了y m结果数组越界。判断完边界还要判断障碍物和访问标记。方向数组本身不会自动避开障碍物它只是“建议的位置”是否采纳这个建议由你的业务逻辑决定。3.2 BFS层序遍历中的方向数组配合BFS 的核心是“逐层扩展”网格 BFS 的核心是“从当前层格子出发用方向数组生成下一层格子”。这里有一份直接可用的模板queuepairint,int q; q.push({startX, startY}); vis[startX][startY] 1; int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); 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 (vis[nx][ny] || grid[nx][ny] ! 1) continue; vis[nx][ny] 1; q.push({nx, ny}); } }这套代码最大的价值是“顺序稳定”先判断边界再判断访问标记最后入队。方向数组的循环放在中间整体结构像流水线一样每一格的状态处理完才进入下一格。这里建议把访问标记写在入队之前不要等到出队再标记否则同一层可能有多个格子重复入队既慢又可能死循环。这类问题我在后面会详细展开。层数统计通常是 BFS 的标准需求。方向数组在这里承担的角色依然是“生成邻居”但配合step变量就能算出从起点到任意位置的最短步数。每次循环遍历当前队列的所有元素内层再枚举方向层数计数器加一int step 0; while (!q.empty()) { int size q.size(); while (size--) { auto [x, y] q.front(); q.pop(); // 方向数组扩展... } step; }步数统计和方向数组没有直接关系但有一个容易忽略的坑如果你用方向数组循环把同一层的多个格子都扩展出来那么这些“新格子”的步数应当等于当前层数加一不能直接写入它们的初始步数。所以更推荐在入队时用dist[nx][ny] dist[x][y] 1来记录省掉层序大小统计也不容易出错。3.3 DFS路径搜索中的方向数组配合DFS 用方向数组的方式跟 BFS 略有不同。BFS 关注“扩展到哪些格子”DFS 关注“沿着一个方向走到黑再回头”。模板大概是void dfs(int x, int y, vectorvectorchar board) { // 先处理当前格子 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (越界 || 已访问 || 不满足条件) continue; vis[nx][ny] 1; dfs(nx, ny); vis[nx][ny] 0; // 回溯 } }DFS 的方向数组有一个“回退”特性如果你在寻找一条路径而不仅仅是在染色连通区域那vis标记必须在递归返回后撤销。不撤销的话这条路径走到死路回退时另一个分支会以为某些格子已经访问过从而漏掉可行路线。很多经典问题如单词搜索、迷宫找路的调试现场一半时间都耗在这种“回溯时机”上。方向数组在 DFS 里还能做一个优化改变遍历顺序。比如在迷宫问题中想让路径优先向下或向右就把方向数组排成先枚举下、右后枚举上、左。这样找到的第一条路径就会偏向右下角。这个技巧在竞赛里叫“启发式调整方向顺序”方向数组是它的直接载体。3.4 方向数组与坐标压缩把二维变一维的实操网格题的另一个常见需求是记录走过的路径或者判重。方向数组生成的是二维坐标但有些场景下二维坐标的vis数组会浪费空间——比如地图很大但实际可走的格子很少。这时可以用哈希表配合坐标编码。把(x, y)编码成整数方向数组照用判重却从bool vis[1005][1005]变成unordered_setint seen。int encodePos(int x, int y) { return x * totalCols y; } // 使用时 int key encodePos(nx, ny); if (seen.count(key)) continue; seen.insert(key);这里的编码方式可以随便设计只要保证每个(x, y)映射到的整数唯一。通常取总列数作为乘数就足够。方向数组跟坐标编码配合之后整套代码可以少写很多层vectorvectorbool的嵌套性能也更稳定尤其适合窄长型地图和多源搜索。4. 方向数组的易错点与问题实录4.1 方向写错、配对错上下左右画成“十字还是叉”方向数组最常见的错误就是把 dx/dy 配对写串。比如 dx 数组写的是{-1, 1, 0, 0}dy 数组写的是{1, 0, -1, 0}虽然四个方向都覆盖了但排列的顺序可能是“左下右乱序”不是严格的上右下左。如果你不依赖顺序问题不大如果依赖比如做螺旋遍历、转向模拟顺序错乱会导致路径直接偏掉。我强烈建议把方向数组的注释写清楚或者在写之前先画一个二维坐标系。通常约定行坐标向下增加矩阵的直觉列坐标向右增加那“上”就是(-1,0)“下”就是(1,0)“左”就是(0,-1)“右”就是(0,1)。我见过不少人把行和列搞反把“上”写成(0,-1)结果整个搜索路径变成斜着走。四方向还好八方向配错就更难查了。4.2 对角线方向处理不当八方向斜着穿墙八方向最经典的问题是“斜线穿墙”。假设一个地图里墙在(0,1)和(1,0)你在(0,0)想走到(1,1)。如果允许八方向移动按道理可以直接斜着走到(1,1)但很多题目要求“不能斜穿墙”也就是斜对角移动还要检查两个相邻的直方向是不是都通畅。方向数组本身不会自动帮你做这个检查你得在生成斜向邻居时额外补一下。封堵斜穿墙的写法通常是在循环里判断if (abs(dx[i]) 1 abs(dy[i]) 1) { if (grid[x dx[i]][y] 1 || grid[x][y dy[i]] 1) continue; }这里的思路是斜向走的必要条件是它两侧的直角方向都能通行。如果没做这层检查看似只是方向数组多定义了几个方向结果整个地图的连通性都变了最短路径、连通区域全都会算错。4.3 访问标记时机BFS 入队前还是出队前很多人在 BFS 里把 vis 标记写在出队的时候逻辑是“我访问到它了才标记”。单看好像也没错但在网格图里同一个格子可能被当前层的多个方向同时发现。如果只在出队时标记就意味着这个格子会被入队多次。队列里存储了大量重复坐标浪费空间不说最致命的是步数统计会乱第一次入队时步数是3等到它真正出队时可能已经有一堆同层异层的格子插到前面了算出来的最短距离自然不对。正确做法是在入队前标记或者说一旦“生成这个新坐标并确认合法”就立刻写入访问标记vis[nx][ny] 1; q.push({nx, ny});这样同一个格子永远不会被第二次入队。方向数组循环里遇到已访问的直接跳过效率高且正确性好。我在代码里经常顺手写成vis[nx][ny] vis[x][y] 1而不是单独开布尔数组一次到位既标记又记录距离但这个习惯需要你对 BFS 的语义足够熟新手还是先分开写比较稳。4.4 DFS 回溯里的方向数组执行时机DFS 的方向数组执行时机比 BFS 更敏感。回溯式搜索要求在递归回来后恢复现场但这个“恢复现场”有顺序讲究。假设你在dfs(x, y)里枚举i0..3每次dfs(nx, ny)返回后执行vis[nx][ny] 0那这个撤销只针对本次尝试的方向不影响下一个方向。有些人误把撤销放在方向数组循环外面结果第一个方向试完就把所有标记全清了后续方向全都变成“从没访问过”死循环和重复路径轮番上阵。一个值得分享的小技巧是用vis[x][y]作为当前路径的占用标记但用另一层布尔数组或状态变量做“已搜索过”的剪枝。也就是说方向数组负责生成候选回溯标记负责还原路径而全局剪枝标记负责告诉程序“这个格子的所有可能性已经试完了不用再进”。三者职责分开调试时脉络就清晰多了。4.5 方向数组索引越界别忘了负数的存在方向数组生成的新坐标可能是负数。如果地图是 0-based(0,0)的上方邻居是(-1,0)这一步没有访问标记可以判断必须靠边界检查拦下来。有些人在边界检查里写x 0 x n y 0 y m这会把左边界和上边界漏掉导致(-1,0)混进逻辑里后面所有操作都错位。正确写法是同时带上 0的判断宁可多写两个条件也别省成x 0 y 0。5. 方向数组的扩展玩法与个人经验5.1 马的遍历用方向数组模拟“日字形”方向数组不止是上下左右和斜对角。国际象棋里的马走日其实也可以用方向数组优雅地表达。马的八种走法行偏移上下各两格、列偏移左右各一格或者行偏移一格、列偏移两格组合出来正好八个方向int horseDx[] {-2, -2, -1, -1, 1, 1, 2, 2}; int horseDy[] {-1, 1, -2, 2, -2, 2, -1, 1};只要把方向数组换掉其余 BFS/DFS 的框架一点不用动。这个例子说明方向数组的本质是“一组可行的状态转移增量”具体是几方向、长什么样完全由题目决定。甚至“飞机可以在几个方向之间飞”“小人可以跳几步”也都能抽象成方向数组。学会这个抽象之后很多看似花哨的移动规则最后都落在同一个模板里。5.2 多源BFS与方向数组同时铺开的搜索多源 BFS 是指队列初始化时塞入多个起点。常见场景是“多个着火点同时蔓延”“多个出口同时找最近起点”。方向数组在这里的作用没有变化依然是生成邻居但多源 BFS 会跟方向数组产生一个有趣的配合初始把所有源点都压进队列然后一层层扩展每个格子的距离记录里天然包含了“最近的源点是哪一个”。如果你在方向数组生成的邻居入队时顺便记录一下它的来源编号就可以得到每个格子归属于哪个源点。这个扩展在竞赛题“多个办公区共享快递柜选址”里很常见。方向数组定义得越标准多源覆盖的逻辑越不容易出错。5.3 方向数组与状态压缩当方向本身是状态时有一些题目把“当前方向”也当作状态的一部分例如“机器人需要右转才能进入某区域”“车头朝向影响转弯半径”。这时我通常会把方向数组设计成“状态机”而非单纯的“邻居生成器”。办法很简单方向数组记四个朝向dir从0到3表示上右下左顺时针。左转是(dir 3) % 4右转是(dir 1) % 4向当前方向前进则是直接使用dx[dir]和dy[dir]。这时候方向数组的定义顺序就绝不能是随便写的必须按特定顺序排列否则取模运算对应不上。这种写法我经常用在模拟“蚂蚁爬行”“清扫机器人”的题目上。方向数组已经不只是“图遍历的工具”而是“状态转移的一等公民”。5.4 调试方向数组问题的小经验最后分享几个我实测很管用的调试技巧第一方向数组写完之后先在纸上画一遍。用起点(0,0)走一次方向数组把中间结果写下来。比如四方向定义成{0, 0, 1, -1}和{1, -1, 0, 0}走一遍就是(0,1)、(0,-1)、(1,0)、(-1,0)正好覆盖右、左、下、上。如果纸上的结果跟你预期不一致那就不是“代码 bug”而是方向数组定义本身的 bug改起来也快。第二如果遍历结果错乱第一步先打印每个新坐标而不是直接去调搜索逻辑。把方向数组循环单独拎出来跑一圈看看有没有重复覆盖、有没有超出边界、有没有漏掉某个方向。我遇到过好几次以为自己搜索逻辑写错了调试半天最后发现是 dy 数组里某个元素从1误写成了-1。第三用“访问顺序”可视化。在vis[nx][ny] 1前后打印当前坐标和方向索引如果发现某个方向的访问次数特别少那大概率是方向数组里那个方向的增量定义有问题或者是边界条件把合法方向过滤掉了。实践下来这个办法比单纯盯代码有效率得多。方向数组这套东西说难不难说简单也容易翻车。很多数据结构与算法的书里不会花一整章讲它但它嵌在 DFS、BFS、状态搜索、多源扩展里几乎跑不掉。做算法题这几年我最大的体会是越基础的概念越值得你把定义吃透因为后面所有复杂解法都在这个地基上搭。能把方向数组的“增量组合”理解成“图的状态转移”很多所谓的难题其实只是加了点约束条件的网格遍历而已。
