企业官网建设流程全解析

我当年刷东华OJ的时候，正好卡在这一段题号上，94、95、97到100，六道题断断续续磨了小半个月。回头去看，这六道题放在一起其实是一条非常清晰的算法能力进阶线，前面两道是搜索入门，后面四道直接把你往DFS和BFS的深水区里推。这篇文章不打算一句一句贴题解，那是题解网站干的事，我更想聊聊这六道题背后通吃的思路、代码模板、剪枝手法，以及我实际踩过之后才明白的坑。不管你是正在刷东华OJ应付考试，还是刚接触算法想找一条扎实的训练路径，这一段题目都有值得拆的价值。

先给这六道题画一个整体轮廓。94和95是典型的回溯入门题，考察的是DFS递归里“尝试-标记-递归-撤销”这一整套节奏，对应的核心数据结构是递归栈和标记数组。97到100题型开始分化，有迷宫最短路径类的BFS、有状态压缩搜索、有连通块统计，还有一个我印象里处理起来最烦的边界模拟。它们共同的前提是你得先吃透“怎么在二维网格上做深度优先和广度优先遍历”，否则后面每道题都会像无头苍蝇。好消息是，一旦你把这几道题啃下来，东华OJ后续一大票搜索题基本都能复用同一套思路。

1. 先把94和95这两道回溯题彻底拿捏

很多人刷题习惯直接上代码，但我建议先把“回溯”这件事的本质想清楚。回溯本质上就是在一棵隐式的决策树里做深度优先遍历，走到死路了就回头换一条路。写递归函数的时候你只需要反复问自己三件事：当前这一步能做什么选择、这个选择合不合法、做完选择之后下一步应该往哪走。每一次递归调用代表一次决策，每一次函数返回代表撤销这次决策，这就是回溯的全部秘密。

拿94题和95题举例，这两道都是N皇后问题的变体，一个是让N个皇后互不攻击，一个是要求输出所有摆放方案。N皇后是回溯算法里最经典的训练题，没有之一，因为它同时考验三件事：递归函数的参数设计、合法性的快速判断、以及对剪枝时机的敏感度。我最初写N皇后的时候犯过一个特别低级的错误：在DFS每一层里重新算一遍当前棋盘上所有皇后的攻击范围，结果N稍微一大就超时。后来才意识到，对于皇后的“列冲突”和“主对角线和副对角线冲突”，完全可以各自用一个布尔数组来记录，判断的时候是O(1)的。

这道题的正确思路是这样的：准备三个标记数组，col[i]表示第i列是否已经被占用，d1[i + j]表示主对角线是否被占用，d2[i - j + n]表示副对角线是否被占用。逐行放置皇后，从第0行走到第n-1行，每一行只需要遍历所有列，找到一个没有被列、主对角线、副对角线三个方向同时封锁的位置，放下去，标记数组更新，递归进入下一行，等递归返回后再把标记恢复。这个“恢复现场”的动作就是回溯最核心的精髓，漏了它，你的结果会指数级爆炸。

对于94题这种只需要输出摆放方案数量的版本，剪枝其实没有太多花活，三个标记数组已经把约束条件卡得死死的，遍历全部合法方案就行。但95题如果要求按字典序或者特定格式输出所有方案，就需要注意你自己的遍历顺序。列循环从0到n-1自然就是字典序，别画蛇添足去排序。如果你发现输出结果顺序和题目要求对不上，优先检查遍历顺序，而不是去写一个多余的排序函数。

我调试N皇后时的一个独家技巧是：先画一张小棋盘，比如N等于4或者5，手动在纸上把所有合法方案列出来，然后让程序输出结果，和你手写的结果一一比对。这样比对过两三道题之后，你对回溯的理解会有一个质的飞跃，远比自己瞎改代码有效率。另一个容易忽略的细节是输入输出格式，很多OJ对空格和换行的卡得极严，94题这种只要数字的方案题倒是还好，95题如果要求方案之间空行，一个不谨慎就会Presentation Error。

2. 97到100题的真实难度分层

说完了94和95，接下来说说97到100这四道。很多人刷到97题的时候会有一个明显的感受：前面的套路不灵了。这个感觉是正常的，因为从97题开始，搜索不再只发生在“模拟棋盘”里，而是真正进入了“网格模型”。

97题在东华OJ的序列里是一个分水岭，它第一次要求你在一张给定的地图上做连通区域的统计。本质上就是遍历整张图，每遇到一个没有访问过的合法格子，就从它开始做一次DFS或者BFS，把所有和它相邻的合法格子全部标记为已访问，计数器加一，然后继续扫描。这个题型是后续刷领域大法的地基，为什么这么说？因为你之后做岛屿数量、积水问题、扫雷展开，全靠这手基础功。

98题和99题则进入了搜索路径问题的领域，核心是求出从起点到终点的最短步数。这类题有一个铁律那就是必须用BFS，不能用DFS，因为DFS不保证遇到终点的路径最短，它找的是“一条可行路径”而不是“最短路径”。虽然DFS在某些特殊限定下也能蒙对，但一旦地图稍微大一点、障碍稍微复杂一点，DFS直接超时到怀疑人生。BFS做最短路径的原理其实很朴素：从起点出发，一层一层向外扩散，第几层扩展到终点，最短步数就是几。这个“层数等于距离”的性质是BFS在无权图上求解最短路径的理论基础。

这两道题写代码时，最需要练的是方向数组和队列的使用。方向数组一般写成dx[4] = {-1, 1, 0, 0}，dy[4] = {0, 0, -1, 1}，配合双层循环枚举四个方向，每次产生新的坐标后，先检查新坐标是否越界，再检查是不是墙或者已经访问过，都没问题才入队。这套“坐标合法性检查”的手感如果练不出来，后续学更复杂的图论算法时会非常吃力，因为所有网格搜索题的根都在这里。

100题是这几道里最有意思的一道，它典型地考察了你对“搜索入口”的识别能力。它给的不是一张规整的方格地图，而是需要你从题目描述里自己抽取出“搜索起点”和“搜索目标”的数学模型。换句话说，100题检验的不只是你会不会写BFS或者DFS，而是你能不能从自然语言描述中看出这道题本质上是一道搜索题。题目会描述一些实体化的场景，比如某种物体的扩散路径或者某种状态的转换条件，你需要自己建立状态表示和状态转移规则。这其实是竞赛和考试之间最大的分水岭，考试题通常把“起点、终点、规则”都画好给你，但竞赛题需要你自己建模。

我个人的经验是，做100题这类题时，先别着急写代码，花10分钟用纸笔画一下状态图。节点是什么、边是什么、起点在哪里、终点在哪里、有没有特殊规则，全部画清楚了再动手。很多同学一上来就写代码，写到一半发现状态定义错了，推翻重来，反而浪费更多时间。

3. 六道题背后的三个统一模板

刷完这段题之后我有一个感受，不管题目的包装怎么变，搜索题其实就那么几个固定套路。只要你把模板内化成肌肉记忆，新题拿到手，套模板的时间和思考的时间几乎可以对半开。

第一个通用模板是深度优先遍历DFS的递归框架。它的结构在任何题里都是相似的：递归函数里先做终止条件判断，然后遍历所有可能的选择，每个选择前检查合法性，合法就做出选择、递归调用、撤销选择。我在前面说到N皇后时已经展示过这个框架了，98题的“判断能不能继续走”本质上也是同一套判断逻辑，甚至更简单。唯一的变化在于递归传参，有的题需要传当前坐标，有的题需要传当前步数，有的题需要传当前收集到的状态值，搞清楚每一层递归需要什么参数，DFS就成功了一半。

第二个通用模板是广度优先遍历BFS的队列模板。初始化一个队列，把起点放进去，记录起点的访问状态，然后while循环，不断弹出队首元素，遍历四个方向，产生新状态，校验合法后放入队尾，直到队列为空或者找到目标。这个模板的变种主要在“状态”上，97题的BFS每个状态是一个坐标，100题的一个状态可能是一个坐标加一个方向，或者一个坐标加一个剩余步数。队列里存的是什么，决定了这道题的搜索空间有多大，这是考量一个人写BFS是否熟练的最重要指标。

第三个模板相对隐蔽，叫做“搜索状态的去重”。凡是你写的BFS或者DFS出现了超时，大概率都是在状态判重上出了问题。有的题需要标记二维坐标，有的题需要标记坐标加方向，有的题需要标记坐标加剩余能量。标记的维度不够，就会导致大量重复搜索，指数级膨胀；标记的维度过多，又会浪费内存和时间。这个平衡需要靠做题量来建立感觉，没有任何人第一次就能完美拿捏。

在97到100这套题里，如果只能带走一个东西，我希望你带走的是“状态设计”的意识。坐标系本身不是状态的全部，状态是你在写代码时定义的一个元组，它必须覆盖所有影响后续决策的信息。一旦漏了信息，你的程序就会在某个测试点上给你演出“答案错误”甚至“死循环”的戏码。

4. 调试搜索题时最值得留意的坑

调试搜索题和调试普通线性逻辑题完全是两种体验。普通题你可以一步步printf看变量变化，搜索题一旦递归层数堆起来，想要靠打印来定位问题几乎等于是大海捞针。我总结了几个刷这段题时踩过的最典型的坑，按出现的频率排序，写在这里供你参考。

第一个坑是标记数组初始化遗漏。97题让你统计连通区域，如果你只初始化了一部分visited数组，另一部分保留着上一次测试数据的残值，那你的计数结果会像是掷骰子。尤其是有多组测试数据的题目，每一组数据之间必须确保所有全局数组重置干净。我用的是C语言风格的三维数组时特别容易漏，比如visited[n][m]在n和m随输入变化的情况下，memset的行数要按实际行数重置，别想着一次性清零。

第二个坑是从队列取出元素和入队时“访问标记”的时机不一致。BFS的正确姿势是在元素入队的那一刻就把它标记为已经访问过，而不是等到它从队列里被弹出来的时候再标记。如果你等到弹出时才标记，同一个节点可能被多个方向同时压入队列，导致重复扩展，轻则增加运行时间，重则让结果错得面目全非。这个坑我在99题里复现了不止一次，后来养成习惯：入队即标记，永远不要依赖“出队时再标记”。

第三个坑是坐标系的混乱。二维数组的行列坐标和数学里的xOy坐标在方向上经常是反的，题目里如果说“向右走一步”，你得想清楚是列号加一还是行号加一。方向数组一旦写错，程序不好好报错，就是在一个区域里兜圈子出不去。我的建议是，在代码最开头用注释写清楚dx和dy分别代表什么方向，每道题写之前都在纸上把坐标系统一画一遍，千万别凭脑子里的旧印象迁移到新题里。

第四个坑是BFS的层级计数问题。97和99题这种要求输出步数的题，有一个经典写法是BFS队列里除了坐标之外还存当前步数，每扩展一步就加一。这个写法没有问题，但有一个变体写法把“步数”保存在一个dist数组里，入队前更新dist[newX][newY] = dist[curX][curY] + 1，这两种写法各有好处，但千万别混用。混用的结果是初始状态步数偏了1，然后所有结果全部偏移。建议你固定使用dist数组法，因为调试时可以直接打印整张dist表来定位问题，比在队列里翻数据直观得多。

第五个坑是输入地图字符串和字符数组的边界问题。东华OJ的地图题很多是给一行行字符串，你读完之后，grid[i][j]的范围是0到n-1，千万不要把grid[i]当成一个字符串去比较，要用下标访问单个字符。有些同学在做和围墙相关的变形题时，喜欢在地图外面再包一圈“墙”，此时数组要开成n+2乘m加2的形状，初始化所有边界为墙，再把地图内容填进去。这个“扩了一圈”的写法能省掉大量的越界判断，代码反而更简洁，我在100题的变形地图中使用频率非常高，推荐你也试试。

5. 我的做题顺序建议和心态调整

关于做题顺序，我强烈建议你遵守原题号顺序，不要跳跃。94和95练DFS回溯，96不知道你的语境下具体是哪题，但我跳过它直接说97到100，是因为后面四道题在能力上是连续递进的，97练连通域扫描，98和99练最短路径BFS，100综合建模，这个次序本身就是一条训练梯度，跳着刷很容易卡在某个点上放弃。

这股题做下来，挫败感基本是免不了的。我记得当时99题我自己写了一个多小时没通过，中间反复改方向数组和判断条件，改到后面人都暴躁了。后来我养成一个习惯，每个搜索题写完后不急着提交，先在本地造几个不同规模的数据，把运行结果打印出来逐行验证。这个小步骤看似多花几分钟，实际上能帮我把提交错误的次数降到原来的四分之一。

另一个心态上的体会是：搜索题的运行时间并非越快越好，关键是复杂度可预测。很多同学喜欢上来就套一个“看上去很高级”的优化，比如记忆化搜索加剪枝，但基础BFS都还没写利索。对于初学者来说，编程题先保证能过，再谈优化，这是所有经验里最实用的一条。很多所谓的高级优化，在数据量不够大的情况下根本体现不出优势，反而让代码更难调试。

还有一个小技巧值得单独提一下：东华OJ的题目测试点并不算强，但经常会有边界数据，比如地图只有一行、起点和终点重合、整张图全是墙等。在做题时，一定要手工把这些边界情况跑一遍。我至少遇到两次因为忽略了“起点就是终点”这种情况而扣了分，这种边界点真的是白交的学费。

6. 从这六道题往后看，你的下一步该练什么

如果你已经把947题到100题都刷明白了，我想先恭喜你，因为你已经把搜索题最核心的两个地基打好了。接下来你往哪个方向走，取决于你的具体目标。

如果你是为了准备算法考试或者竞赛，建议把重心转向“状态搜索”这个更深的领域。典型的进阶题是八数码、华容道、推箱子，这类题的特点是搜索状态不再是简单坐标，而是一个棋盘布局甚至一个排列。你需要用哈希或者字符串来表示状态，并用一个结构体来配合BFS做判重，这一步是对你状态设计能力的真正考验。东华OJ上这样的题也有一批，刷完100题之后接着刷，你会明显感觉到自己写代码的“建模能力”在快速提升。

如果你是为了数据结构课程的期末考试，那100题之后可以适当转向并查集和最小生成树相关的题目。并查集在网格问题中应用十分广泛，尤其在连通性和动态连通性题目里，它的代码比DFS更简洁，运行效率也更高。换句话说，97题教会了你DFS统计连通域，但未来考试里要求你快速回答“两个格子是否连通”时，并查集才是真正的答案。

如果你想在这个方向继续深挖，我个人建议从“最短路径”系列入手。用BFS做完99题之后，你可以考一考自己：如果把地图加上不同权重的通行代价，怎么办？这时候经典的Dijkstra算法就要登场了。你会发现在Dijkstra的实现里，优先队列替代了普通BFS的队列，dist数组从“最小步数”升级成“最小代价”，但整体框架和BFS仍然保持高度的同构。学到这里，你已经能从搜索题无缝过渡到图论题了，之前刷的每一道题都会变成你后续学习的台阶。

7. 最后分享一点我个人的做题心法

说了这么多干货，最后聊点不那么技术但挺管用的感受。刷东华OJ这一段题，最重要的不是把六道题过掉就完事，而是在这个过程中真正培养“拆题建模”的思维习惯。一条题目拿到手里，强迫自己先给出三个问题的答案：状态怎么表达、转移怎么发生、终点怎么判断。这三问答得上来，代码基本就已经在脑子里写完了，键盘上的工作只是把它敲出来而已。

我个人在实际做题中体会最深的一件事是，搜索题的代码模板非常固定，但你绝不能只背模板。我聊过的好几个学弟学妹都有一个共同的困境，就是模板背得溜，遇到新题还是不会套。原因在于模板只是骨架，真正的血肉是每道题的状态定义和转移逻辑。你写每一道新题的时候，都应当重新从“拆题建模”开始走一遍流程，而不是按捺不住地直接打开编辑器把模板先敲一遍。当你发现自己拿到新题后，看一眼就能自然地调整模板、增减字段、改造约束条件时，这段题才算真正刷到位了。

最后再分享一个小习惯：我会把自己每道题的错误记录在一个笔记里，记录内容包括错误类型、定位过程、修正方案，而不是简简单单标注一个“过”。东华OJ这套题目对于初学者最大的价值，不在于最后的Accept标记，而在于调试过程中对问题本质的琢磨和反思。这六道题我至今还记得每道题的坑，就是因为当时动笔记录过，这些记录在后来的工作里还真的帮了我几次，这大概是刷题之外最有价值的副产品了。