题目简述

给定一个 n×m的迷宫，'o'表示可走，'#'表示障碍。老鼠从左上角 (1,1)出发，要到达右下角 (n,m)。移动规则是：每一步优先尝试右、下、左、上（固定顺序），如果某个方向能走就走过去，否则依次尝试下一个方向；如果四个方向都走不了，就回溯到上一步选择其他方向。需要输出所有可能的路径（按找到的顺序），每条路径用 ->连接坐标。如果没有任何路径，输出 "no"。

解题思路

本题要求输出所有可能的路径，且搜索顺序固定，显然要用深度优先搜索（DFS）配合回溯法。DFS 会沿着一条路径走到黑，走不通就退回岔路口换一条路，直到穷举所有可能性。由于迷宫尺寸很小（n,m ≤ 10），DFS 完全可行。

关键点：

方向顺序必须是 右→下→左→上，否则输出顺序与题目要求不符。

使用 vis数组标记已走过的格子，防止原地转圈。

用数组或 vector记录当前路径上的坐标，到达终点时输出整条路径。

回溯时必须撤销标记，否则其他路径无法经过该格子。

DFS 通用模板

DFS 的本质是一种递归遍历，模板如下：

cpp 下载 复制 void dfs(当前状态) { if (达到目标状态) { 处理结果（如记录、输出）； return； } for (所有可能的下一步选择) { if (选择合法) { 标记当前选择； 更新状态； dfs(新状态)； 恢复状态（回溯）； } } }

各部分作用：

参数：通常包含位置、步数、累计值等，依问题而定。

终止条件：当状态满足题目要求时，进行结果处理并返回。

循环遍历：枚举所有可行的下一步操作，例如移动方向、选择物品等。

合法性检查：判断下一步是否在边界内、是否已访问、是否满足约束等。

标记与递归：执行选择后标记（如设置 vis为 true），然后递归进入下一层。

回溯：递归返回后撤销标记，恢复状态，以便尝试其他分支。

本题的 DFS 实现分析 状态定义

当前位置 (x, y)

当前路径长度 step（已经走了几步，从 0 开始计）

终止条件

当 x == n && y == m时，找到一条完整路径，输出并返回。

选择与合法性

四个方向按顺序（右、下、左、上）生成新坐标 (xx, yy)。合法性条件：

xx在 [1, n]范围内

yy在 [1, m]范围内

格子为 'o'

未被访问过（vis[xx][yy] == 0）

标记与回溯

将新坐标加入路径数组，标记 vis[xx][yy] = 1

递归调用 dfs(xx, yy, step+1)

递归返回后，将 vis[xx][yy]重置为 0（回溯）

输出格式

路径坐标用 ->连接，最后一个坐标不加箭头。例如：1,1->2,1->3,1。

代码关键片段

下面是 DFS 函数的核心代码（不含全局变量声明和主函数）：

cpp 下载 复制 void dfs(int x, int y, int step) { if (x == n && y == m) { ans++; cout << ans << ":"; for (int i = 0; i < step - 1; i++) cout << peth[i][0] << "," << peth[i][1] << "->"; cout << peth[step-1][0] << "," << peth[step-1][1] << endl; return; } for (int i = 0; i < 4; i++) { int xx = x + b[i], yy = y + a[i]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && as[xx][yy] == 'o') { peth[step][0] = xx; peth[step][1] = yy; vis[xx][yy] = 1; dfs(xx, yy, step + 1); vis[xx][yy] = 0; } } }

说明：

a[4] = {1, 0, -1, 0}和 b[4] = {0, 1, 0, -1}分别表示列偏移和行偏移，顺序为右、下、左、上。

peth是二维数组，peth[step][0]和 peth[step][1]分别存储第 step步的横纵坐标。

vis标记格子是否走过。

ans统计路径总数，输出时作为序号。

主函数流程

读入 n、m和迷宫地图。

将起点 (1,1)标记为已访问，并存入路径数组的第一个位置。

调用 dfs(1, 1, 1)（此时 step=1表示路径中已有起点）。

搜索结束后，若 ans == 0，输出 "no"。

注意事项

方向顺序：必须严格按照右、下、左、上，否则输出顺序错误。

回溯：vis标记必须在递归后清除，否则会遗漏其他路径。

路径存储：使用数组 peth配合 step索引，输出时注意最后一个坐标不加箭头。

数组大小：peth至少能存下最长路径（n,m≤10，最长路径不超过100步），开 255足够。

边界条件：起点和终点保证不是 '#'，无需额外判断。

样例验证

以题目样例输入：

复制 6 5 ooooo o#### ooooo #oo#o oooo# o#ooo

程序输出 8 条路径，与题目给出的输出完全一致。若迷宫无解（例如被 #包围），则输出 "no"。

总结

本题通过 DFS + 回溯，按固定方向顺序枚举所有路径。理解 DFS 模板和回溯思想是关键。代码实现时注意方向顺序和输出格式，即可顺利通过。DFS 不仅适用于迷宫，还可推广到排列组合、子集、数独等众多问题中，是算法竞赛的基础技能。

同时，附上上一期题解的代码

#include<bits/stdc++.h> using namespace std; int main(){ int n,x,y; cin>>n>>x>>y; if(x>y){ cout<<n-1; return 0; } if(y%x==0) cout<<n-y/x; if(y%x!=0){ if(n-y/x-1<0) cout<<0; else cout<<n-y/x-1; } return 0; } 下期将在2026.7.23颁布题解，同时附上激动的代码

顺便提一句，那个赚钱代码谨慎运行！！！！！！