题目描述

Amber 学姐正在开发一款名为“异世界旅行者”的游戏。为了确保游戏原型的稳定性，她决定先实现一个传统的网格寻路算法。角色只能在上、下、左、右四个方向移动，且不能穿过障碍物。请帮助 Amber 学姐实现这个寻路算法，找出从起点到终点的最短路径。

输入格式

第一行：两个整数 $m$ 和 $n$，表示地图的行数和列数（$1 \le m, n \le 100$）

接下来 $m$ 行：每行 $n$ 个整数，表示地图数据：

• $0$ 表示可行走区域

• $1$ 表示障碍物

最后一行：四个整数 $x_{start}, y_{start}, x_{end}, y_{end}$，表示起点坐标 $(x_{start}, y_{start})$ 和目标点坐标 $(x_{end}, y_{end})$

输出格式

从起点开始，输出最短路径上的每一个点的坐标 $(x, y)$，按顺序输出

坐标格式：每行两个整数，用空格分隔

如果无法从起点到达目标点，输出 "No path"（不含引号）

样例数据

输入 #1

8 8
0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 0 0 0
0 0 0 1 1 1 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0
0 0 7 7

输出 #1

0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 7
2 7
3 7
4 7
5 7
6 7
7 7

说明/提示

坐标系统：左上角为 $(0,0)$，$x$ 表示行号（向下递增），$y$ 表示列号（向右递增）

移动规则：每次只能向上、下、左、右移动一个格子

路径应该是最短的可行路径

出题人：Amber Aeolian