1. 迷宫寻路：信息学奥赛的经典挑战
迷宫问题在信息学奥赛中就像数学考试里的必考题，几乎每年都会以不同形式出现。我第一次参加NOI集训时，教练就说过："不会解迷宫题，就像战士不会用枪。"这话虽然夸张，但确实点出了迷宫问题在算法竞赛中的基础地位。
为什么迷宫问题如此重要？因为它完美融合了图论遍历和最短路径两大核心算法思想。OpenJudge平台上《走出迷宫》这道题，就是典型的二维矩阵迷宫问题。题目要求从起点'S'出发，找到通往终点'T'的最短路径，其中'#'代表墙壁不可通过，'.'代表通路。
实际解题时，新手常犯的错误是直接使用深度优先搜索（DFS）。我刚开始也这么干过，结果在小地图上跑得挺快，一旦遇到20x20以上的迷宫就卡死了。后来才明白，DFS的时间复杂度是O(n!)，而广度优先搜索（BFS)能稳定在O(n)。举个例子，5x5的迷宫用DFS可能1秒出结果，但10x10的迷宫能让普通电脑算上几个小时。
2. 广度优先搜索的核心思想
2.1 广搜的"波浪"理论
理解BFS最形象的比喻是"往池塘里扔石头"。想象你把起点位置当作石头投入水中，波纹会一圈圈均匀扩散——这就是BFS的核心：等距离探索。在代码中，这个"波纹"就是队列（queue）数据结构。
我常用的可视化方法是给迷宫每个格子标记访问顺序。比如一个3x3迷宫：
1 2 3 4 5 6 7 8 9这就是典型的BFS访问顺序，就像水波从左上角均匀扩散。而DFS则会像钻洞一样一条路走到黑，可能是1-2-3-6-9-8-5-4-7。
2.2 代码模板的五个关键部件
根据OpenJudge上《走出迷宫》的AC代码，我提炼出BFS的通用模板结构：
- 方向数组：
dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}代表上下左右四个方向 - 访问标记：
vis[N][N]数组避免重复访问 - 队列结构：存储位置(x,y)和当前步数s
- 边界检查：判断新坐标是否越界
- 终止条件：到达终点时立即返回步数
特别提醒新手注意vis数组的设置时机。我见过很多WA代码是因为在出队时才设置vis为true，这会导致同一位置被多次入队。正确的做法是在入队前就标记访问，就像官方题解中的vis[x][y] = true在que.push之前执行。
3. 从模板到实战的细节优化
3.1 输入处理的坑点
原题的输入格式看似简单：
n m 地图数据...但实际编码时有三个易错点：
- 地图行列索引从1还是0开始？（本题是1-based）
- 字符读取时注意换行符（建议用cin>>自动跳过）
- 起点'S'和终点'T'的位置记录
我的调试技巧是首先打印整个地图，确保读取正确。曾经有一次比赛，我因为没发现测试数据末尾有多余空格，导致读取错位，白白浪费半小时。
3.2 内存与效率的平衡
NOI竞赛中常见的迷宫尺寸上限是100x100，这时vis数组用bool类型足够。但如果遇到1000x1000的迷宫（如某些省选题目），就需要考虑：
- 使用
bitset压缩空间 - 方向数组改用静态常量
- 队列预分配内存
在OpenJudge的在线评判系统中，还要注意C++的queue可能比手写循环队列慢。对于时间卡得很紧的题目，可以用vector模拟队列。
4. 广搜与深搜的实战对比
4.1 时间复杂度实测
我用同一台机器测试了5x5到20x20的随机迷宫：
| 迷宫尺寸 | BFS时间(ms) | DFS最短路径时间(ms) |
|---|---|---|
| 5x5 | 0.12 | 0.15 |
| 10x10 | 0.35 | 12.7 |
| 15x15 | 0.98 | 超时(>60s) |
| 20x20 | 2.1 | 超时(>60s) |
可以看出，当迷宫尺寸增大时，DFS的劣势呈指数级增长。这是因为DFS必须探索所有可能路径才能确定最短路线，而BFS第一次遇到终点时就能确保是最短路径。
4.2 适用场景分析
虽然BFS在迷宫寻路中占优，但DFS在以下情况仍有用武之地：
- 需要记录完整路径而不仅是步数
- 迷宫带有特殊规则（如传送门、钥匙门）
- 求路径总数而非最短路径
建议新手先掌握BFS模板，再学习DFS的优化技巧如记忆化、剪枝等。就像学数学先背乘法口诀，再学速算技巧。
5. OpenJudge评测注意事项
OpenJudge系统对《走出迷宫》这类题目的评判有几个特点：
- 严格匹配输出格式（本题只需输出一个数字）
- 多测试用例连续评判（需要每次重置
vis数组） - 时间限制通常是1秒（C++代码足够）
我建议在本地测试时：
- 准备边界用例（如1x1迷宫）
- 测试无解情况（修改题目要求）
- 检查内存泄漏（虽然OJ一般不判这个）
遇到WA时，可以用这个小数据测试：
3 3 S.. ##. ..T正确输出应该是4（绕两个弯），而错误代码可能输出2（直线距离）。
6. 算法扩展与变式训练
掌握了基础迷宫问题后，可以尝试这些变式：
- 多起点单终点（逆向BFS）
- 携带状态搜索（如破墙次数）
- 分层图搜索（三维迷宫）
- 优先队列优化（Dijkstra思想）
NOI近年来的趋势是结合其他算法形成复合题，比如：
- 迷宫+动态规划（路径计数）
- 迷宫+贪心（最优资源收集）
- 迷宫+并查集（连通块分析）
建议从OpenJudge的"迷宫"标签下选择不同难度题目练习，我个人的训练路径是：基础BFS→多状态BFS→双向BFS→A*算法，每个阶段保证刷10道以上题目。
