迷宫问题

Time Limit: 1000 ms

Memory Limit: 65535 kb

[显示标签]

Description

设计一个程序解决迷宫问题,迷宫中可通行的格子置为1,不可通行的格子置为0;由于此迷宫是由石头做成,所以只可以前后左右前进,要求:求出最短路径所经过的格子数,并将不可通行以及四周的格子置为’#’,最短路径置为’*’,剩余可通行格子置为’@’,并输出此矩阵,每个格子间用空格隔开,若有多条路径,输出最上面一条。若无可行路径,输出“no pace!”

Input

第一行:迷宫的行和列(整数,n<=10);(i,j);接下来i行输入迷宫矩阵;接下来两行分别输入入口和出口的行与列。

Output

第一行:最短路径格子数;接下来第i+2行输出经变动后的迷宫矩阵,并输出最短路径的每个格子的坐标;若无最短路径只输出”no pace!”

Sample Input

5 5
1 0 0 0 0
1 1 1 1 0
0 1 0 1 0
0 1 1 1 1
1 1 0 0 1
1 1
5 5

Sample Output

9
# # # # # # #
# * # # # # #
# * * * * # #
# # @ # * # #
# # @ @ * * #
# @ @ # # * #
# # # # # # #
(1,1)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4)(4,5)(5,5)

Hint

None

Source

YangWen

提交代码