企业官网建设流程全解析

咱们刷题、准备408的，或者写过一段算法代码的朋友，应该都被这类问题卡过：走迷宫、扫雷、岛屿数量、单词搜索……看起来题目千变万化，但解法掉进网格之后，翻来覆去就是那几个操作——往上下左右挪一步，判断出没出界，再决定要不要接着递归或入队。这个“往哪挪一步”的动作，就是图论里最不起眼却最不能错的基础设施之一：方向数组。

方向数组也叫方向增量数组、位移数组，本质就是一组预先定义好的坐标偏移量。它可以被当成“网格建图”的桥梁，也可以直接放进BFS/DFS的遍历框架里。很多新手能看懂深搜宽搜的概念，一到手写代码就栽在方向数组上：要么顺序写错，要么边界判断漏了，要么八方向的时候把斜对角和上下左右混在一起。这篇文章就把方向数组的定义、几种写法、配套的踩坑经验都捋一遍，适合正在学数据结构与算法、准备考研复试、复习期末《数据结构》，或者在刷题平台上卡在网格类题目的朋友。

1. 方向数组的本质：网格也是一张图

1.1 为什么需要方向数组：二维网格的“邻接表”

很多人学图论的时候，脑子里默认的图是邻接矩阵或者邻接表：V个点，E条边，点与点之间靠链表或二维数组相连。可实际上有一大类图长得特别规整——矩阵、棋盘、迷宫、地图，每个格子就是图里的顶点，格子和格子之间是否相连，取决于它们是否在物理位置上相邻。

这种图不需要显式地存储“谁和谁相连”，因为相邻关系是可以算出来的。一个格子(x, y)，它的四个邻居无非就是(x+1, y)、(x-1, y)、(x, y+1)、(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 按下标一一配对，这四个方向无论怎么排列，逻辑上都是一样的。把“上下左右”翻译成“行坐标增量为-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_set<int>或者一维int[]直接做访问标记，查找效率比set<pair<int,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 的核心是“从当前层格子出发，用方向数组生成下一层格子”。这里有一份直接可用的模板：

queue<pair<int,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, vector<vector<char>>& 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_set<int> 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)映射到的整数唯一。通常取总列数作为乘数就足够。方向数组跟坐标编码配合之后，整套代码可以少写很多层vector<vector<bool>>的嵌套，性能也更稳定，尤其适合窄长型地图和多源搜索。

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)里枚举i=0..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、状态搜索、多源扩展里，几乎跑不掉。做算法题这几年，我最大的体会是：越基础的概念，越值得你把定义吃透，因为后面所有复杂解法都在这个地基上搭。能把方向数组的“增量组合”理解成“图的状态转移”，很多所谓的难题，其实只是加了点约束条件的网格遍历而已。