A70649. 迷宫的路径
编程题
提高
知识点
题目描述
Mitch老鼠在森林里游玩，不小心走进了一个迷宫里面，这个迷宫是一个 n 行 m 列的矩阵，迷宫中有些格子是可以走的，有些格子是不能走的，能走的格子用 o （小写字母 o ）表示，不能走的格子用 # 表示。
Mitch选择走出迷宫的策略是：先向右，如果右边走不通则选择向下，如果下边走不通则选择向左，如果左边走不通则选择向上；如果四个方向都走不通，则后退选择其他能走的路径。
Mitch从类似下图所示的迷宫的左上角 (1,1) 点进入迷宫（请注意：入口 1,1 和出口的 n,m 点都不是 # ），请问Mitch有哪些方法可以走出迷宫，走到 (n,m) 点；请编程求出所有可能的路径，输出这些路径，如果不存在任何的路径可以走出迷宫，请输出 no。
输入格式
第一行包含两个整数 n 和 m ，中间用单个空格隔开，代表迷宫的行和列的数量。
接下来 n 行，每行 m 个字符，描述迷宫地图。字符只有o 或 # 两种，o 代表这个格子可以走，# 代表这个格子不能走。( 4 ≤ n,m ≤ 10 )
输出格式
请按照Mitch选择的走出迷宫的策略，输出所有可能的路径，输出形式请参考样例输出的形式。
如果不存在任何的路径可以走出迷宫，请输出 no。
输入输出样例
输入 #1
6 5 ooooo o#### ooooo #oo#o oooo# o#ooo
输出 #1
1:1,1->2,1->3,1->3,2->3,3->4,3->5,3->5,4->6,4->6,5 2:1,1->2,1->3,1->3,2->3,3->4,3->5,3->6,3->6,4->6,5 3:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->5,4->6,4->6,5 4:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->6,3->6,4->6,5 5:1,1->2,1->3,1->3,2->4,2->4,3->5,3->5,4->6,4->6,5 6:1,1->2,1->3,1->3,2->4,2->4,3->5,3->6,3->6,4->6,5 7:1,1->2,1->3,1->3,2->4,2->5,2->5,3->5,4->6,4->6,5 8:1,1->2,1->3,1->3,2->4,2->5,2->5,3->6,3->6,4->6,5
说明/提示
## 思路
「迷宫的路径」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。
「迷宫的路径」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。