#7067. 【提高】迷宫的路径 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Mitch老鼠在森林里游玩,不小心走进了一个迷宫里面,这个迷宫是一个 n 行 m 列的矩阵,迷宫中有些格子是可以走的,有些格子是不能走的,能走的格子用 o (小写字母 o )表示,不能走的格子用 # 表示。

Mitch选择走出迷宫的策略是:先向右,如果右边走不通则选择向下,如果下边走不通则选择向左,如果左边走不通则选择向上;如果四个方向都走不通,则后退选择其他能走的路径。

Mitch从类似下图所示的迷宫的左上角 (1,1)(1,1) 点进入迷宫(请注意:入口 1,11,1 和出口的 n,mn,m 点都不是 # ),请问Mitch有哪些方法可以走出迷宫,走到 (n,m)(n,m) 点;请编程求出所有可能的路径,输出这些路径,如果不存在任何的路径可以走出迷宫,请输出 no。

输入格式

第一行包含两个整数n和m,中间用单个空格隔开,代表迷宫的行和列的数量。
接下来n行,每行m个字符,描述迷宫地图。字符只有“o”或“#”两种,“o”代表这个格子可以走,“#”代表这个格子不能走。(4 <= n,m <= 10 )

输出格式

请按照Mitch选择的走出迷宫的策略,输出所有可能的路径,输出形式请参考样例输出的形式。

样例

样例输入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