1. 项目概述从四道OJ题看C算法核心思维最近在带学生刷题集中处理了几个经典的OJ题目分别是数根、进制转换、迷宫出口和迷宫最少步数。这几个题乍一看领域不同但内核都是对C基础语法和核心算法思维的绝佳训练。很多初学者在学完语法后面对实际问题依然无从下手问题就出在“思维转换”上——如何把生活或数学问题翻译成计算机能理解和执行的步骤。这四道题恰好覆盖了从简单模拟到经典搜索的完整进阶路径非常适合用来构建解题的“肌肉记忆”。今天我就以这四题为例拆解背后的核心思路、常见陷阱和代码实现细节希望能帮你打通从“看懂”到“做出”的任督二脉。2. 题目深度解析与核心思路拆解2.1 2791: 【入门】数根——理解“模拟”与“数位分离”数根Digital Root是一个经典的数学概念也是一个绝佳的“模拟”类入门题。题目通常会这样描述给定一个正整数反复将其各位数字相加直到得到一个个位数这个个位数就是该数的数根。核心思路拆解这道题考察的核心能力是“循环”与“数位分离”。很多新手一上来就想找数学公式确实存在即dr(n) 1 ((n - 1) % 9)但对于入门练习题目本意是希望我们用模拟的过程来理解计算机的运算逻辑。思路分为两层循环外层循环判断当前数字n是否已经是个位数即n 10。如果不是就需要进入内层循环进行数位求和。内层循环将一个非个位数的n通过% 10和/ 10操作分离出每一位数字并累加。为什么选择模拟而非公式对于初学者直接使用公式会错过两个重要的训练点一是“数位分离”这一基础编程技巧这是处理数字相关问题的基石二是对“循环终止条件”的把握。模拟过程能让你清晰地看到数据是如何一步步变化的这对于调试和理解程序流至关重要。在实际竞赛或面试中如果被要求“实现”数根面试官也更期望看到你扎实的基本功而不是直接调用一个结论。一个容易忽略的边界数字0。根据定义0的数根是0。但在模拟过程中如果n初始为0外层循环条件while (n 10)不会进入直接返回0这是正确的。但如果使用do...while循环就需要特别注意处理0的情况避免死循环或错误结果。这是题目常见的陷阱点。2.2 2627: 【基础】进制转换——掌握“除基取余”与“栈”的应用进制转换是计算机科学的基础这道题通常要求将十进制整数转换为指定的K2 K 16进制数。这不仅仅是数学计算更是数据结构栈的经典应用场景。核心思路拆解“除基取余逆序排列”这是十进制转K进制的标准算法。以十进制数N转二进制为例N % 2得到最低位余数。N N / 2更新N。重复步骤1和2直到N为0。将每次得到的余数逆序连接起来就是最终的二进制表示。为什么需要“逆序”因为计算过程是从低位最右边向高位最左边进行的而我们读取数字的习惯是从左到右。这个“逆序”操作天然契合栈Stack这种数据结构“后进先出”LIFO的特性。我们可以将每次的余数压入栈中计算结束后再依次弹出弹出的顺序自然就是正确的顺序。处理大于10的进制如16进制当K大于10时余数可能为10、11...它们需要对应地表示为字母‘A‘、’B‘...。这里通常用一个字符数组或字符串作为映射表char digitMap[] 0123456789ABCDEF;。这样余数remainder直接作为下标digitMap[remainder]就是对应的字符。这种方法比写一堆if-else判断要优雅和高效得多。一个关键细节处理负数与零。题目通常规定输入是非负整数。但作为一种良好的编程习惯需要考虑零的情况十进制数0转换为任何进制都是“0”。如果不对0进行特殊处理按照“除基取余”的循环条件while (N 0)将不会产生任何输出导致错误。因此在循环开始前应判断if (N 0)直接输出“0”。2.3 3301: 【基础】迷宫出口——深度优先搜索(DFS)的直观引入迷宫问题是我们接触搜索算法的第一个“实战”场景。3301这道题通常只要求判断从起点能否到达终点而不关心具体路径或最短距离这正好是深度优先搜索DFS最典型的应用。核心思路拆解递归与回溯我们可以把迷宫看作一个二维网格每个格子要么是路用0表示要么是墙用1表示。从起点开始我们尝试朝四个方向上、下、左、右探索。递归函数设计函数dfs(x, y)表示从坐标(x, y)开始搜索。终止条件如果(x, y)就是终点则找到出口返回成功。如果(x, y)是墙或已经走过或者越界则此路不通返回失败。标记与探索如果当前位置是路且未走过先将其标记为“已访问”例如将值从0改为2防止后续重复走到这里导致死循环。然后递归地调用dfs函数向四个方向分别尝试。回溯在某个方向的递归调用返回后继续尝试下一个方向。这里不需要在递归返回后将标记清除因为本题只问“能否到达”一个格子走过之后无论从哪条路径来的都不需要再走第二次。这与需要找所有路径或最短路径的问题不同。DFS的优缺点与本题的适配性DFS的实现非常直观代码简洁特别适合解决“连通性”问题两点是否连通。它的缺点是如果迷宫很大且路径复杂递归深度可能过深导致栈溢出。但对于OJ题目的常规数据范围DFS通常足够。这道题用DFS来实现逻辑清晰是理解递归搜索思想的完美起点。重要注意事项方向数组的使用。为了代码整洁我们通常定义一个方向数组int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右这样通过一个循环就能遍历四个方向避免写四段相似的代码既减少了出错概率也便于维护。2.4 3303: 【基础】走出迷宫的最少步数——广度优先搜索(BFS)的必然选择当迷宫问题从“能否走出”升级为“最少步数走出”时DFS就不再是最优解了。因为DFS会一条路走到黑它找到的第一条路径很可能不是最短的。要保证找到最短路径必须使用广度优先搜索BFS。核心思路拆解队列与层次遍历BFS的核心思想是“层层推进”。它从起点开始先探索所有距离为1步的点再探索所有距离为2步的点以此类推。当第一次遇到终点时当前的层数步数就是最短步数。数据结构使用队列Queue来存储待探索的节点。每个节点需要记录其坐标(x, y)以及从起点到该点的步数step。初始化将起点坐标和步数0入队并标记起点为已访问。循环探索当队列不为空时取出队首节点。如果该节点是终点则其step即为答案搜索结束。否则遍历其四个方向的邻居。如果邻居是路且未访问过则将其坐标和step1入队并标记为已访问。为什么BFS能找到最短路径因为BFS是按距离起点由近及远的顺序访问节点的。假设最短路径长度为L那么所有长度小于L的路径上的点都会在终点之前被访问到。当BFS第一次访问到终点时不可能存在一条比当前路径更短的路径否则终点应该更早被访问到。BFS与DFS在迷宫问题中的本质区别搜索顺序DFS是“深度优先”钻到底再回头BFS是“广度优先”平铺开来。数据结构DFS用递归栈或显式栈BFS用队列。解的特性DFS不能保证最先找到的解是最优解最短路径BFS只要路径代价是均匀的如每步代价为1就一定能找到最优解。空间开销在最坏情况下BFS需要存储一整层的节点空间开销可能大于DFS。实现关键点步数的记录。在BFS中有两种常见方式记录步数在结构体/节点中记录如上所述每个节点保存自己的步数。新节点的步数 父节点步数 1。使用距离数组用一个与迷宫同尺寸的二维数组dist[][]初始化所有值为-1表示未访问。dist[startX][startY] 0。当从(x, y)扩展到(nx, ny)时dist[nx][ny] dist[x][y] 1。这种方法逻辑清晰且最终dist[endX][endY]就是答案。对于3303这类标准的最少步数问题使用距离数组是更通用和推荐的做法。3. 代码实现与逐行精讲3.1 数根2791的两种实现对比我们先从最直接的模拟法开始实现。版本一双重循环模拟#include iostream using namespace std; int digitalRoot(int n) { // 外层循环当n不是个位数时继续 while (n 10) { int sum 0; // 内层循环分离n的每一位并求和 while (n 0) { sum n % 10; // 取个位数加到sum n / 10; // 去掉个位数 } n sum; // 将求和后的值赋给n进行下一轮判断 } return n; } int main() { int num; cin num; // 直接处理输入为0的情况虽然循环也能处理但这样逻辑更清晰 cout digitalRoot(num) endl; return 0; }逐行精讲while (n 10)这是外层循环的条件。只要n还是两位数或以上就需要继续计算数位和。注意这里是10因为10是第一个两位数。int sum 0;在每一轮外层循环开始时初始化本轮的累加器。while (n 0)这是内层循环用于拆解当前n的每一位。n % 10取得当前n的个位数n / 10相当于整数除法去掉已经处理的个位。当n被除到0时所有数位都处理完毕。n sum;一轮内层循环结束后sum存储了原始n的数位和。将这个和赋值给n回到外层循环的起点进行判断。如果此时n仍大于等于10则继续下一轮。版本二单循环与公式法#include iostream using namespace std; int digitalRootSingleLoop(int n) { while (n 10) { // 在单次循环中同时完成求余、求和、更新n // 这个技巧在循环内计算数位和时很常见 int sum 0; for (int t n; t 0; t / 10) { sum t % 10; } n sum; } return n; } int digitalRootFormula(int n) { // 数学公式dr(n) 0 if n0 else 1 ((n-1) % 9) // 注意处理n0的情况 if (n 0) return 0; return 1 ((n - 1) % 9); } int main() { int num; cin num; // 可以尝试调用不同的函数进行比较 cout digitalRootSingleLoop(num) endl; // cout digitalRootFormula(num) endl; return 0; }关键点对比单循环版将内层的while循环改为了for循环逻辑完全一样但用for循环的初始化、条件、迭代三部分来表达“对一个数的每一位进行操作”的意图对某些读者来说可能更清晰。公式版这是基于数论性质的O(1)解法。理解这个公式需要知道一个数模9的余数除了0等于其数根除了9本身数根9对应余数0。1 ((n-1) % 9)这个公式巧妙地处理了余数为0时对应数根9的情况因为(9-1)%98, 189。但在OJ练习中除非题目明确要求效率或作为知识拓展否则建议优先实现模拟法以巩固基础。3.2 进制转换2627的完整实现与细节处理下面是一个健壮的十进制转K进制实现考虑了零、负数虽然题目可能不要求和大于10的进制。#include iostream #include stack using namespace std; string decimalToKBase(int N, int K) { // 处理0的情况必须单独处理 if (N 0) { return 0; } // 处理负数先按正数转换最后加负号 bool isNegative false; if (N 0) { isNegative true; N -N; // 转换为正数处理注意INT_MIN取负会溢出这里假设题目范围不包含它 } // 数位映射表支持最高16进制 const char digitMap[] 0123456789ABCDEF; stackchar s; // 用于逆序存储结果的栈 // 除基取余过程 while (N 0) { int remainder N % K; // 求余数 s.push(digitMap[remainder]); // 余数转换为对应字符并入栈 N / K; // 更新N为商 } // 构造结果字符串 string result; if (isNegative) { result.push_back(-); // 如果是负数添加负号 } while (!s.empty()) { result.push_back(s.top()); // 栈顶是最高位 s.pop(); } return result; } int main() { int N, K; cin N K; // 输入验证确保K在合理范围内 if (K 2 || K 16) { cout K must be between 2 and 16. endl; return 1; } cout decimalToKBase(N, K) endl; return 0; }逐行精讲与避坑指南零值处理第7-10行这是最容易遗漏的边界条件。如果输入N为0while (N 0)循环不会执行栈为空最终结果将是空字符串。因此必须在循环前判断并直接返回0。负数处理第13-18行虽然很多OJ题目规定输入是非负整数但作为一个通用函数处理负数是有意义的。方法是先记录符号然后对N的绝对值进行转换。特别注意对于有符号整数的最小值如INT_MIN直接取负会导致溢出。在严格的工业代码中需要将N转换为long long类型或使用无符号数来处理。OJ题目通常数据范围友好但要知道这个陷阱。数位映射表第21行digitMap是一个字符数组下标0-15正好对应字符‘0‘-’9‘和’A‘-’F‘。使用映射表比写if (remainder 10) ... else ...要简洁高效得多也更容易扩展到更高进制只需扩展映射表。栈的使用第22-30行stackchar完美适配了“后进先出”的需求。余数从低位到高位依次计算但输出需要从高位到低位。压栈push再弹栈pop的过程自动完成了逆序。结果构造第33-40行从栈中依次取出字符追加到结果字符串result的末尾。如果之前判断是负数记得在字符串最前面加上负号。不使用栈的替代方案也可以先将结果计算到一个字符串中最后用reverse函数反转字符串。或者递归实现在递归返回后输出余数也能达到逆序效果。但使用栈是最直观体现“逆序”这一数据结构特性的方法。3.3 迷宫出口3301的DFS递归实现假设迷宫输入格式为第一行两个整数R和C表示行数和列数接着是一个R行C列的0/1矩阵最后一行四个整数startX, startY, endX, endY表示起点和终点坐标通常坐标从1开始而数组下标从0开始需要转换。#include iostream #include vector using namespace std; int R, C; // 迷宫行数和列数 vectorvectorint maze; // 迷宫地图0可走1为墙 vectorvectorbool visited; // 访问标记数组 int startX, startY, endX, endY; // 方向数组上下左右 int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; bool dfs(int x, int y) { // 1. 终止条件到达终点 if (x endX y endY) { return true; } // 2. 标记当前点为已访问 visited[x][y] true; // 3. 向四个方向尝试探索 for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 检查新坐标(nx, ny)是否合法且可走且未访问 if (nx 0 nx R ny 0 ny C maze[nx][ny] 0 !visited[nx][ny]) { // 递归探索如果找到出口直接返回true if (dfs(nx, ny)) { return true; } // 如果这条路径没找到会回溯到此处继续尝试下一个方向 // 注意本题不需要“撤销访问标记”因为一个格子走过一次就不用再走了 } } // 4. 四个方向都走不通返回false return false; } int main() { cin R C; maze.resize(R, vectorint(C)); visited.resize(R, vectorbool(C, false)); // 初始化访问数组为false // 读入迷宫注意题目坐标可能从1开始这里假设输入就是数组下标 for (int i 0; i R; i) { for (int j 0; j C; j) { cin maze[i][j]; } } cin startX startY endX endY; // 如果题目坐标从1开始需要转换为从0开始startX--; startY--; ... // 检查起点终点是否本身就是墙虽然题目通常保证不是但防御性编程是好的 if (maze[startX][startY] 1 || maze[endX][endY] 1) { cout No endl; return 0; } if (dfs(startX, startY)) { cout Yes endl; } else { cout No endl; } return 0; }逐行精讲与核心技巧全局变量 vs 参数传递这里将迷宫大小、地图、访问数组、方向数组等定义为全局变量是为了在递归函数dfs中访问方便避免层层传递多个参数。在竞赛编程中这是一种常见且高效的写法。但在大型工程中应避免滥用全局变量。递归函数返回值设计dfs函数返回bool类型表示从当前点(x, y)出发能否到达终点。这种设计使得一旦在某条路径上找到终点可以通过层层返回true快速结束整个搜索。访问标记的时机在判断到达终点之后才将当前点标记为已访问。这个顺序很重要。如果先标记那么当起点就是终点时会被错误地标记为已访问然后直接返回false。当然也可以在函数开头标记但需要先判断(x, y)是否为终点。递归中的“回溯”代码中注释提到了“回溯”。在本实现中“回溯”体现在递归调用dfs(nx, ny)返回后程序会继续循环尝试下一个方向。注意这里并没有显式地“撤销”visited[nx][ny]的标记。这是因为本题只关心连通性一个格子只要被访问过一次无论从哪条路径来的都不需要再访问第二次。这种“不撤销标记”的DFS其访问过的区域相当于被“填充”了不会重复搜索效率更高。方向数组的妙用使用dir数组和循环来处理四个方向是搜索题的标准写法。它极大地减少了重复代码也使得代码更容易扩展到八个方向。3.4 走出迷宫的最少步数3303的BFS队列实现同样假设类似的输入格式现在要求输出最短步数如果无法到达则输出-1。#include iostream #include vector #include queue using namespace std; int R, C; vectorvectorint maze; // 距离数组同时兼任访问标记的功能-1表示未访问 vectorvectorint dist; int dir[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int bfs(int startX, int startY, int endX, int endY) { // 初始化距离数组为-1 dist.assign(R, vectorint(C, -1)); // 使用队列元素为pairx, y queuepairint, int q; // 起点入队并设置距离 dist[startX][startY] 0; q.push({startX, startY}); while (!q.empty()) { // 取出队首元素 auto [x, y] q.front(); q.pop(); // 如果到达终点立即返回距离 if (x endX y endY) { return dist[x][y]; } // 遍历四个方向 for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 检查新坐标是否合法、是路、且未访问过 if (nx 0 nx R ny 0 ny C maze[nx][ny] 0 dist[nx][ny] -1) { // 新点的距离等于当前点距离加1 dist[nx][ny] dist[x][y] 1; // 新点入队等待后续探索 q.push({nx, ny}); } } } // 队列为空仍未找到终点说明不可达 return -1; } int main() { cin R C; maze.resize(R, vectorint(C)); for (int i 0; i R; i) { for (int j 0; j C; j) { cin maze[i][j]; } } int startX, startY, endX, endY; cin startX startY endX endY; // 同样注意坐标转换问题 cout bfs(startX, startY, endX, endY) endl; return 0; }逐行精讲与BFS特性分析距离数组dist的双重作用dist[x][y]不仅记录了从起点到(x, y)的最短距离其值是否为-1还直接表示了该点是否被访问过。这种“一石二鸟”的做法在BFS中非常常见简洁高效。队列的使用queuepairint, int存储待探索的坐标。pair在这里很方便。注意我们没有在队列元素中存储步数因为步数信息已经保存在dist数组中了。当从(x, y)扩展到(nx, ny)时dist[nx][ny]可以直接由dist[x][y] 1得到。BFS的核心循环第20-40行while (!q.empty())只要还有待探索的点就继续。auto [x, y] q.front(); q.pop();C17的结构化绑定方便地取出队首坐标。相当于int x q.front().first; int y q.front().second; q.pop();。终点判断在从队列中取出一个点时立即判断它是否为终点。由于BFS是按距离递增的顺序访问节点的所以第一次遇到终点时dist[x][y]一定是最短距离。扩展邻居对四个方向进行探索。关键条件是dist[nx][ny] -1这确保了每个点只被入队一次从而保证了距离是最短的。如果某个点之前已经被访问过dist值不为-1那么当前这条路径到达它的距离一定不会比之前记录的更短因为BFS是层层推进的所以无需再次入队。返回值如果函数执行完while循环队列变空都没有返回说明起点和终点不连通返回-1。BFS为什么能找到最短路径的直观理解想象一下向平静的水面投入一颗石子涟漪一圈圈扩散出去。BFS就像这个涟漪起点是石子落点。距离起点为1的点第一圈涟漪会先被访问到然后是距离为2的点第二圈涟漪……当涟漪第一次碰到终点时它所经历的圈数就是最短距离。因为如果存在一条更短的路径终点应该属于更内圈的涟漪会先被碰到。4. 常见错误、调试技巧与性能优化4.1 四道题共通的“坑点”与排查清单数组下标越界这是迷宫类问题33013303最常见的错误。在访问maze[nx][ny]或dist[nx][ny]之前必须先检查nx和ny是否在[0, R)和[0, C)的范围内。忘记检查会导致程序运行时访问非法内存引起崩溃或不可预知的行为。坐标体系混淆题目描述的坐标常常从(1, 1)开始而C数组下标从(0, 0)开始。在读入起点终点坐标后务必记得减1再传入搜索函数。这是一个非常低级的错误但很多人会忘。输入格式处理仔细阅读题目输入说明。迷宫地图可能每行数字是连在一起的如0110也可能用空格隔开。使用cin读取整数会自动处理空格但如果数字是连在一起的就需要按字符读取再转换。务必根据题目样例调整输入代码。死循环与栈溢出DFS中如果忘记标记已访问的点visited数组或者标记了但在回溯时错误地清除了标记对于仅判断连通性的问题不需要清除会导致程序在两个点之间来回走陷入无限递归最终栈溢出Segmentation fault 或 Runtime Error。BFS中如果忘记标记已访问的点即更新dist数组会导致同一个点被重复加入队列无数次队列会无限膨胀最终内存超限Memory Limit Exceeded。初始化问题visited或dist数组没有正确初始化。特别是全局变量在多次测试用例时如果不在每个用例开始时重新初始化上一个用例的数据会污染下一个用例。输出格式题目要求输出“YES/NO”、“Yes/No”还是“1/0”要求输出最短步数如果不可达是输出“-1”还是“Impossible”仔细看题避免因格式错误导致判题系统判为错误。4.2 调试技巧如何定位搜索算法中的问题当你的DFS/BFS代码提交后得到错误答案WA或运行时错误RE时可以按以下步骤排查小数据测试自己构造一个非常小的迷宫比如3x3在纸上手动模拟你的算法一步步跟踪变量的变化visited/dist数组、队列内容等看是否与程序输出一致。输出中间状态在DFS/BFS函数中关键位置添加临时输出语句。对于DFS在进入递归函数时打印当前坐标(x, y)。在返回前打印返回值。这可以帮助你看到递归的路径和深度。对于BFS在每次从队列中取出节点时打印该节点坐标和距离。在将新节点入队时也打印其坐标和距离。这可以让你看清BFS的扩展过程。重要提交最终代码前记得删除这些调试输出。检查边界和起点终点单独测试起点就是终点的情况、起点或终点是墙的情况、迷宫只有一行或一列的情况。这些边界情况往往是出题人设计测试点的地方。使用静态分析工具如果是在本地IDE如Visual Studio Code、CLion中编程利用编译器的警告信息-Wall -Wextra和代码静态检查功能可以发现一些潜在问题如未使用的变量、有符号无符号比较等。4.3 从这四题出发的性能优化思考对于OJ题目给定的数据范围通常R, C在100-500量级上述的标准DFS/BFS实现已经足够快。但了解优化思路对解决更复杂的问题有帮助DFS的迭代实现递归DFS代码简洁但递归调用有函数调用开销且深度过大会栈溢出。可以使用一个显式的栈stackpairint, int来实现迭代版本的DFS从而避免递归深度限制。对于3301这种连通性问题迭代DFS和递归DFS在逻辑上是等价的。BFS的双向搜索当迷宫很大且起点和终点距离较远时可以从起点和终点同时开始BFS。当两个搜索的“前沿”相遇时路径长度就是两边距离之和。这通常能将搜索范围减半对于超大迷宫有奇效。但这道题通常不需要。使用更快的输入输出当需要读入大量数据时比如1000x1000的迷宫使用cin/cout可能会比较慢。可以关闭同步流ios::sync_with_stdio(false);并解除cin和cout的绑定cin.tie(nullptr);或者直接使用scanf/printf。这在算法竞赛中是一个常用技巧。空间优化对于BFS我们使用了dist二维数组。如果迷宫非常大这可能占用较多内存。有时可以复用maze数组用特殊值如-2表示未访问-1表示墙非负数表示距离来记录距离和状态但会牺牲一些代码清晰度。5. 举一反三题目变种与思维延伸刷题的目的不是记住这几道题的答案而是掌握其背后的思维模式并能应用到其他问题上。5.1 数根问题的变种多次查询如果题目要求对海量的数字进行数根查询那么每次都用模拟法计算就会超时。此时可以预处理1到9的数根就是本身或者直接使用数根公式dr(n) 1 ((n-1) % 9)进行O(1)查询。这体现了“空间换时间”和“数学优化”的思想。计算数根和求一个区间内所有数的数根之和。这可能需要你找出数根在区间内的分布规律而不是傻傻地遍历求和。5.2 进制转换的延伸K进制转十进制这是反向操作原理是“按权展开累加求和”。例如一个K进制数S字符串形式其十进制值value 0从最高位开始value value * K (当前位数字对应的数值)。任意进制间转换一种通用的方法是先转到十进制作为中介再从十进制转到目标进制。这需要你实现上述两种转换。小数部分的进制转换这涉及到乘K取整和精度控制是另一个有趣的课题。5.3 迷宫/搜索问题的经典变种掌握了基础的DFS和BFS你就打开了图论和搜索算法的大门。以下是一些直接的延伸求具体路径3301进阶不仅要判断能否走出还要记录走的路径。在DFS中可以用一个数组path记录每一步的选择或者在回溯时保存路径。在BFS中需要额外一个pre数组记录每个点是从哪个点扩展来的最后从终点反向追溯到起点。有多把钥匙的迷宫迷宫中有些门需要对应的钥匙才能打开。状态就不再仅仅是坐标(x, y)而是(x, y, keyState)其中keyState是一个二进制数表示当前拥有的钥匙集合。这变成了一个状态空间搜索问题依然可以用BFS解决但状态维数增加了。求最短路径的条数在BFS求最短距离的基础上再维护一个ways数组记录到达每个点的最短路径数量。当从点A扩展到点B时如果第一次访问Bdist[B] -1则ways[B] ways[A]。如果通过另一条同样短的路径再次访问Bdist[B] dist[A] 1则ways[B] ways[A]。网格中的连通块问题求迷宫中有多少个独立的、由“路”构成的连通区域。这被称为“种子填充法”或“Flood Fill”。从一个未访问的路点开始DFS或BFS标记所有能到达的点为同一个连通块然后计数加一再找下一个未访问的路点。这是许多图像处理和分析算法的基础。把这四道题吃透理解每一步为什么这么做遇到变种时你就能快速识别出这是“数位分离”、“除基取余”、“DFS连通性”或“BFS最短路”的模型然后套用并调整相应的解题框架。这才是刷题训练的核心价值所在。