Description

有一天，小哈一个去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫地图，现在小哼要以最快速度去解救小哈。问题就此开始了……　　迷宫由n行m列的单元格组成，每个单元格要么是空地，要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点到小哈所在位置的最短路径，注意障碍物是不能走的，当然也不能走到迷宫之外。n和m都小于等于100。

Input Format

第一行有两个数N M。N表示迷宫的行，M表示迷宫的列。接来下来N行M列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。

Output Format

一个整数表示小哼到小哈的最短步数。如果不能解救小哈则输出No Way!

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3​

7​

Source

搜索