迷宫最短路径

题目描述

给定一个 n × m 的迷宫，其中 0 表示可以通行，1 表示墙壁。每次只能向上、下、左、右移动一格，不能走出迷宫，也不能经过墙壁。

请输出从入口到出口的一条最短路径；如果没有路径，输出 no way。

输入格式

第一行两个正整数 n, m，表示迷宫的行数和列数。

接下来 n 行，每行 m 个整数 0 或 1，整数之间以空格分隔。

接下来两行，每行两个整数：第一行是入口坐标 (x1, y1)，第二行是出口坐标 (x2, y2)。行号和列号均从 1 开始。

输出格式

如果存在路径，按 (行,列)->(行,列)->... 的格式输出从入口到出口的一条最短路径。

如果没有路径，输出：

no way

输入输出样例 #1

输入 #1

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 0 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
2 1
8 4

输出 #1

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

数据范围与提示

对于全部数据，1 ≤ n, m ≤ 100。

使用 BFS 可以保证第一次到达出口时得到的路径步数最少。为使输出唯一，搜索相邻格子的顺序固定为：右、下、左、上。