F. 【提高】走出迷宫的最短路径

    Type: Default 1000ms 120MiB

【提高】走出迷宫的最短路径

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.

说明

有n*m的迷宫,该迷宫有一个入口,一个出口。编写一程序打印一条从迷宫入口到出口的最短路径,黑色方块的单元表示走不通(用1表示),白色方块的内容表示走的通(用0表示)
只能往上下左右四个方向走,如果有最短路径,保证最短路径一定是唯一的,如果没有路径可以到达,则输出“no way”。

输入格式

第一行输入2个整数n和m(n和m都是10~150之间的整数),代表迷宫的行数和列数
接下来n行,每行有m个整数,1代表不可走的点,0代表可走的点
接下来一行,有2个整数s1和s2代表入口的坐标
接下来一行,有2个整数e1和e2代表出口的坐标

输出格式

输出从入口到出口的最短路径,如果没有路径可达输出“no way”

样例

8 5      
1 1 1 1 1  
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 0 0 1 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
2 1  
8 4
(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)->(5,3)->(6,3)->(6,4)->(7,4)->(8,4)

搜索练习DFS与BFS

Not Claimed
Status
Done
Problem
12
Open Since
2023-2-27 19:45
Deadline
2023-3-8 23:59
Extension
96 hour(s)