从数根、进制转换到迷宫搜索：四道OJ题精讲C++算法核心思维

1. 项目概述：从四道OJ题看C++算法核心思维

最近在带学生刷题，集中处理了几个经典的OJ题目，分别是数根、进制转换、迷宫出口和迷宫最少步数。这几个题乍一看领域不同，但内核都是对C++基础语法和核心算法思维的绝佳训练。很多初学者在学完语法后，面对实际问题依然无从下手，问题就出在“思维转换”上——如何把生活或数学问题，翻译成计算机能理解和执行的步骤。这四道题恰好覆盖了从简单模拟到经典搜索的完整进阶路径，非常适合用来构建解题的“肌肉记忆”。今天，我就以这四题为例，拆解背后的核心思路、常见陷阱和代码实现细节，希望能帮你打通从“看懂”到“做出”的任督二脉。

2. 题目深度解析与核心思路拆解

2.1 2791: 【入门】数根——理解“模拟”与“数位分离”

数根（Digital Root）是一个经典的数学概念，也是一个绝佳的“模拟”类入门题。题目通常会这样描述：给定一个正整数，反复将其各位数字相加，直到得到一个个位数，这个个位数就是该数的数根。

核心思路拆解：这道题考察的核心能力是“循环”与“数位分离”。很多新手一上来就想找数学公式（确实存在，即dr(n) = 1 + ((n - 1) % 9)），但对于入门练习，题目本意是希望我们用模拟的过程来理解计算机的运算逻辑。思路分为两层循环：

1. 外层循环：判断当前数字n是否已经是个位数（即n < 10）。如果不是，就需要进入内层循环进行数位求和。
2. 内层循环：将一个非个位数的n，通过% 10和/ 10操作，分离出每一位数字并累加。

为什么选择模拟而非公式？对于初学者，直接使用公式会错过两个重要的训练点：一是“数位分离”这一基础编程技巧，这是处理数字相关问题的基石；二是对“循环终止条件”的把握。模拟过程能让你清晰地看到数据是如何一步步变化的，这对于调试和理解程序流至关重要。在实际竞赛或面试中，如果被要求“实现”数根，面试官也更期望看到你扎实的基本功，而不是直接调用一个结论。

一个容易忽略的边界：数字0。根据定义，0的数根是0。但在模拟过程中，如果n初始为0，外层循环条件while (n >= 10)不会进入，直接返回0，这是正确的。但如果使用do...while循环，就需要特别注意处理0的情况，避免死循环或错误结果。这是题目常见的陷阱点。

2.2 2627: 【基础】进制转换——掌握“除基取余”与“栈”的应用

进制转换是计算机科学的基础，这道题通常要求将十进制整数转换为指定的K（2 <= K <= 16）进制数。这不仅仅是数学计算，更是数据结构（栈）的经典应用场景。

核心思路拆解：“除基取余，逆序排列”这是十进制转K进制的标准算法。以十进制数N转二进制为例：

1. N % 2得到最低位（余数）。
2. N = N / 2更新N。
3. 重复步骤1和2，直到N为0。
4. 将每次得到的余数逆序连接起来，就是最终的二进制表示。

为什么需要“逆序”？因为计算过程是从低位（最右边）向高位（最左边）进行的，而我们读取数字的习惯是从左到右。这个“逆序”操作天然契合栈（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表示）。从起点开始，我们尝试朝四个方向（上、下、左、右）探索。

1. 递归函数设计：函数dfs(x, y)表示从坐标(x, y)开始搜索。
2. 终止条件：
   • 如果(x, y)就是终点，则找到出口，返回成功。
   • 如果(x, y)是墙或已经走过，或者越界，则此路不通，返回失败。
3. 标记与探索：如果当前位置是路且未走过，先将其标记为“已访问”（例如将值从0改为2），防止后续重复走到这里导致死循环。然后，递归地调用dfs函数，向四个方向分别尝试。
4. 回溯：在某个方向的递归调用返回后，继续尝试下一个方向。这里不需要在递归返回后将标记清除，因为本题只问“能否到达”，一个格子走过之后，无论从哪条路径来的，都不需要再走第二次。这与需要找所有路径或最短路径的问题不同。

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步的点，以此类推。当第一次遇到终点时，当前的层数（步数）就是最短步数。

1. 数据结构：使用队列（Queue）来存储待探索的节点。每个节点需要记录其坐标(x, y)以及从起点到该点的步数step。
2. 初始化：将起点坐标和步数0入队，并标记起点为已访问。
3. 循环探索：当队列不为空时，取出队首节点。
   • 如果该节点是终点，则其step即为答案，搜索结束。
   • 否则，遍历其四个方向的邻居。如果邻居是路且未访问过，则将其坐标和step+1入队，并标记为已访问。
4. 为什么BFS能找到最短路径？因为BFS是按距离起点由近及远的顺序访问节点的。假设最短路径长度为L，那么所有长度小于L的路径上的点都会在终点之前被访问到。当BFS第一次访问到终点时，不可能存在一条比当前路径更短的路径，否则终点应该更早被访问到。

BFS与DFS在迷宫问题中的本质区别：

• 搜索顺序：DFS是“深度优先”，钻到底再回头；BFS是“广度优先”，平铺开来。
• 数据结构：DFS用递归栈（或显式栈），BFS用队列。
• 解的特性：DFS不能保证最先找到的解是最优解（最短路径）；BFS只要路径代价是均匀的（如每步代价为1），就一定能找到最优解。
• 空间开销：在最坏情况下，BFS需要存储一整层的节点，空间开销可能大于DFS。

实现关键点：步数的记录。在BFS中，有两种常见方式记录步数：

1. 在结构体/节点中记录：如上所述，每个节点保存自己的步数。新节点的步数 = 父节点步数 + 1。
2. 使用距离数组：用一个与迷宫同尺寸的二维数组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 n==0 else 1 + ((n-1) % 9) // 注意处理n=0的情况 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)%9=8, 1+8=9）。但在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"; stack<char> 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; }

逐行精讲与避坑指南：

1. 零值处理（第7-10行）：这是最容易遗漏的边界条件。如果输入N为0，while (N > 0)循环不会执行，栈为空，最终结果将是空字符串。因此必须在循环前判断并直接返回"0"。
2. 负数处理（第13-18行）：虽然很多OJ题目规定输入是非负整数，但作为一个通用函数，处理负数是有意义的。方法是先记录符号，然后对N的绝对值进行转换。特别注意：对于有符号整数的最小值（如INT_MIN），直接取负会导致溢出。在严格的工业代码中，需要将N转换为long long类型或使用无符号数来处理。OJ题目通常数据范围友好，但要知道这个陷阱。
3. 数位映射表（第21行）：digitMap是一个字符数组，下标0-15正好对应字符‘0‘-’9‘和’A‘-’F‘。使用映射表比写if (remainder < 10) ... else ...要简洁高效得多，也更容易扩展到更高进制（只需扩展映射表）。
4. 栈的使用（第22-30行）：stack<char>完美适配了“后进先出”的需求。余数从低位到高位依次计算，但输出需要从高位到低位。压栈（push）再弹栈（pop）的过程自动完成了逆序。
5. 结果构造（第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; // 迷宫行数和列数 vector<vector<int>> maze; // 迷宫地图，0可走，1为墙 vector<vector<bool>> 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, vector<int>(C)); visited.resize(R, vector<bool>(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; }

逐行精讲与核心技巧：

1. 全局变量 vs 参数传递：这里将迷宫大小、地图、访问数组、方向数组等定义为全局变量，是为了在递归函数dfs中访问方便，避免层层传递多个参数。在竞赛编程中，这是一种常见且高效的写法。但在大型工程中，应避免滥用全局变量。
2. 递归函数返回值设计：dfs函数返回bool类型，表示从当前点(x, y)出发能否到达终点。这种设计使得一旦在某条路径上找到终点，可以通过层层返回true快速结束整个搜索。
3. 访问标记的时机：在判断到达终点之后，才将当前点标记为已访问。这个顺序很重要。如果先标记，那么当起点就是终点时，会被错误地标记为已访问，然后直接返回false。当然，也可以在函数开头标记，但需要先判断(x, y)是否为终点。
4. 递归中的“回溯”：代码中注释提到了“回溯”。在本实现中，“回溯”体现在递归调用dfs(nx, ny)返回后，程序会继续循环尝试下一个方向。注意：这里并没有显式地“撤销”visited[nx][ny]的标记。这是因为本题只关心连通性，一个格子只要被访问过一次，无论从哪条路径来的，都不需要再访问第二次。这种“不撤销标记”的DFS，其访问过的区域相当于被“填充”了，不会重复搜索，效率更高。
5. 方向数组的妙用：使用dir数组和循环来处理四个方向，是搜索题的标准写法。它极大地减少了重复代码，也使得代码更容易扩展到八个方向。

3.4 走出迷宫的最少步数（3303）的BFS队列实现

同样假设类似的输入格式，现在要求输出最短步数，如果无法到达则输出-1。

#include <iostream> #include <vector> #include <queue> using namespace std; int R, C; vector<vector<int>> maze; // 距离数组，同时兼任访问标记的功能（-1表示未访问） vector<vector<int>> 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, vector<int>(C, -1)); // 使用队列，元素为pair<x, y> queue<pair<int, 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, vector<int>(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特性分析：

1. 距离数组dist的双重作用：dist[x][y]不仅记录了从起点到(x, y)的最短距离，其值是否为-1还直接表示了该点是否被访问过。这种“一石二鸟”的做法在BFS中非常常见，简洁高效。
2. 队列的使用：queue<pair<int, int>>存储待探索的坐标。pair在这里很方便。注意我们没有在队列元素中存储步数，因为步数信息已经保存在dist数组中了。当从(x, y)扩展到(nx, ny)时，dist[nx][ny]可以直接由dist[x][y] + 1得到。
3. BFS的核心循环（第20-40行）：
   • while (!q.empty())：只要还有待探索的点，就继续。
   • auto [x, y] = q.front(); q.pop();：C++17的结构化绑定，方便地取出队首坐标。相当于int x = q.front().first; int y = q.front().second; q.pop();。
   • 终点判断：在从队列中取出一个点时，立即判断它是否为终点。由于BFS是按距离递增的顺序访问节点的，所以第一次遇到终点时，dist[x][y]一定是最短距离。
   • 扩展邻居：对四个方向进行探索。关键条件是dist[nx][ny] == -1，这确保了每个点只被入队一次，从而保证了距离是最短的。如果某个点之前已经被访问过（dist值不为-1），那么当前这条路径到达它的距离一定不会比之前记录的更短（因为BFS是层层推进的），所以无需再次入队。
4. 返回值：如果函数执行完while循环（队列变空）都没有返回，说明起点和终点不连通，返回-1。

BFS为什么能找到最短路径的直观理解：想象一下向平静的水面投入一颗石子，涟漪一圈圈扩散出去。BFS就像这个涟漪，起点是石子落点。距离起点为1的点（第一圈涟漪）会先被访问到，然后是距离为2的点（第二圈涟漪）……当涟漪第一次碰到终点时，它所经历的圈数就是最短距离。因为如果存在一条更短的路径，终点应该属于更内圈的涟漪，会先被碰到。

4. 常见错误、调试技巧与性能优化

4.1 四道题共通的“坑点”与排查清单

1. 数组下标越界：这是迷宫类问题（3301，3303）最常见的错误。在访问maze[nx][ny]或dist[nx][ny]之前，必须先检查nx和ny是否在[0, R)和[0, C)的范围内。忘记检查会导致程序运行时访问非法内存，引起崩溃或不可预知的行为。
2. 坐标体系混淆：题目描述的坐标常常从(1, 1)开始，而C++数组下标从(0, 0)开始。在读入起点终点坐标后，务必记得减1再传入搜索函数。这是一个非常低级的错误，但很多人会忘。
3. 输入格式处理：仔细阅读题目输入说明。迷宫地图可能每行数字是连在一起的（如0110），也可能用空格隔开。使用cin读取整数会自动处理空格，但如果数字是连在一起的，就需要按字符读取再转换。务必根据题目样例调整输入代码。
4. 死循环与栈溢出：
   • DFS中：如果忘记标记已访问的点（visited数组），或者标记了但在回溯时错误地清除了标记（对于仅判断连通性的问题不需要清除），会导致程序在两个点之间来回走，陷入无限递归，最终栈溢出（Segmentation fault 或 Runtime Error）。
   • BFS中：如果忘记标记已访问的点（即更新dist数组），会导致同一个点被重复加入队列无数次，队列会无限膨胀，最终内存超限（Memory Limit Exceeded）。
5. 初始化问题：visited或dist数组没有正确初始化。特别是全局变量，在多次测试用例时，如果不在每个用例开始时重新初始化，上一个用例的数据会污染下一个用例。
6. 输出格式：题目要求输出“YES/NO”、“Yes/No”还是“1/0”？要求输出最短步数，如果不可达是输出“-1”还是“Impossible”？仔细看题，避免因格式错误导致判题系统判为错误。

4.2 调试技巧：如何定位搜索算法中的问题

当你的DFS/BFS代码提交后得到错误答案（WA）或运行时错误（RE）时，可以按以下步骤排查：

1. 小数据测试：自己构造一个非常小的迷宫（比如3x3），在纸上手动模拟你的算法，一步步跟踪变量的变化（visited/dist数组、队列内容等），看是否与程序输出一致。
2. 输出中间状态：在DFS/BFS函数中关键位置添加临时输出语句。
   • 对于DFS：在进入递归函数时，打印当前坐标(x, y)。在返回前，打印返回值。这可以帮助你看到递归的路径和深度。
   • 对于BFS：在每次从队列中取出节点时，打印该节点坐标和距离。在将新节点入队时，也打印其坐标和距离。这可以让你看清BFS的扩展过程。
   • 重要：提交最终代码前记得删除这些调试输出。
3. 检查边界和起点终点：单独测试起点就是终点的情况、起点或终点是墙的情况、迷宫只有一行或一列的情况。这些边界情况往往是出题人设计测试点的地方。
4. 使用静态分析工具：如果是在本地IDE（如Visual Studio Code、CLion）中编程，利用编译器的警告信息（-Wall -Wextra）和代码静态检查功能，可以发现一些潜在问题，如未使用的变量、有符号无符号比较等。

4.3 从这四题出发的性能优化思考

对于OJ题目给定的数据范围（通常R, C在100-500量级），上述的标准DFS/BFS实现已经足够快。但了解优化思路对解决更复杂的问题有帮助：

1. DFS的迭代实现：递归DFS代码简洁，但递归调用有函数调用开销，且深度过大会栈溢出。可以使用一个显式的栈（stack<pair<int, int>>）来实现迭代版本的DFS，从而避免递归深度限制。对于3301这种连通性问题，迭代DFS和递归DFS在逻辑上是等价的。
2. BFS的双向搜索：当迷宫很大，且起点和终点距离较远时，可以从起点和终点同时开始BFS。当两个搜索的“前沿”相遇时，路径长度就是两边距离之和。这通常能将搜索范围减半，对于超大迷宫有奇效。但这道题通常不需要。
3. 使用更快的输入输出：当需要读入大量数据时（比如1000x1000的迷宫），使用cin/cout可能会比较慢。可以关闭同步流ios::sync_with_stdio(false);并解除cin和cout的绑定cin.tie(nullptr);，或者直接使用scanf/printf。这在算法竞赛中是一个常用技巧。
4. 空间优化：对于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时：
  • 如果第一次访问B（dist[B] == -1），则ways[B] = ways[A]。
  • 如果通过另一条同样短的路径再次访问B（dist[B] == dist[A] + 1），则ways[B] += ways[A]。
• 网格中的连通块问题：求迷宫中有多少个独立的、由“路”构成的连通区域。这被称为“种子填充法”或“Flood Fill”。从一个未访问的路点开始DFS或BFS，标记所有能到达的点为同一个连通块，然后计数加一，再找下一个未访问的路点。这是许多图像处理和分析算法的基础。

把这四道题吃透，理解每一步为什么这么做，遇到变种时你就能快速识别出这是“数位分离”、“除基取余”、“DFS连通性”或“BFS最短路”的模型，然后套用并调整相应的解题框架。这才是刷题训练的核心价值所在。