题目描述

Jill Bates讨厌爬山。Jill无论去哪里都骑自行车，但她总是希望选择最简单且最短的路线。好消息是她住在Greenhills，那里的所有道路都严格按照矩形网格布局：东西向的道路称为街道（streets）南北向的道路称为大道（avenues） 任意两个相邻网格点之间的距离相同。

坏消息是Greenhills多山且有许多单行道。在选择路线时，Jill遵循以下三个规则：

1. 避免相邻网格点之间超过$10$米的海拔爬升
2. 绝不逆行单行道
3. 总是选择最短的可能路线

你的程序需要帮助Jill找到符合条件的路线。

输入格式

输入包含多个地图数据，格式如下：

1. 第一行包含两个整数$n$和$m$（$1 \leq n, m \leq 20$），分别表示街道和大道数量
2. 接下来$n$行给出网格点海拔：每行代表一条街道，包含$m$个用空格分隔的整数 表示该街道沿线网格点的海拔高度（米）
3. 随后是一个或多个定义单向道路的行。每条道路由两对整数表示，格式为：

street avenue street avenue

前两个数字表示道路起点，后两个表示终点如果两点不相邻，则道路会经过所有中间网格点（如样例所示）以四个$0$结束道路定义 第一组街道和大道坐标定义了道路的起点，第二组定义了终点。由于Greenhills采用严格的网格布局，如果两个点在网格中不相邻，道路将经过所有中间的网格点。例如：

5 7 5 8

5 8 5 9 5 9 5 10

表示从$5-7$到$5-8$、$5-8$到$5-9$、以及$5-9$到$5-10$的道路。 4. 最后是一个或多个路径查询行，每行包含两对网格点坐标，格式为：

street avenue street avenue

各整数对之间用一个或多个空格分隔。输入数据的结束以包含四个0的行标记，格式与前述相同。

可以假定所有街道和大道编号都在输入首行定义的范围内，且所有道路定义严格遵循南北或东西方向。

输出格式

对于每个路径查询：输出从起点到终点的网格点序列，格式为street-avenue to street-avenue若存在多个合法路径，输出任意一个即可若无合法路径或起止点相同，输出相应提示信息每组输出间用空行分隔。

输入数据 1

3 4
10 15 20 25
19 30 35 30
10 19 26 20
1 1 1 4
2 1 2 4
3 4 3 3
3 3 1 3
1 4 3 4
2 4 2 1
1 1 2 1
0 0 0 0
1 1 2 2
2 3 2 3
2 2 1 1
0 0 0 0

输出数据 1

1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3, stay put!

There is no acceptable route from 2-2 to 1-1.

提示