#t. 【提高】迷宫的路径?

    Type: Default 1000ms 64MiB

【提高】迷宫的路径?

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

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

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

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


1

2

3

4

5

1

o

o

o

o

o

2

o

#

#

#

#

3

o

o

o

o

o

4

#

o

o

#

o

5

o

o

o

o

#

6

o

#

o

o

o

输入格式

第一行包含两个整数n和m,中间用单个空格隔开,代表迷宫的行和列的数量。

接下来n行,每行m个字符,描述迷宫地图。字符只有“o”或“#”两种,“o”代表这个格子可以走,“#”代表这个格子不能走。(4 <= n,m <= 10 )

输出格式

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

样例

6 5
ooooo
o####
ooooo
#oo#o
oooo#
o#ooo
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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45