#P2226. [HNOI2001] 遥控赛车比赛

[HNOI2001] 遥控赛车比赛

题目描述

全国遥控赛车大赛近日在星沙举行。竞赛选用一块大小为 N×MN\times M 的场地作为竞赛场地,要求选手的赛车在最短的时间内从起点移动到终点。虽然赛场地形高低有少许的起伏,但并不存在无法到达的地点。但是在赛场上增加了许多无法穿越的障碍物,若赛车在到达终点前撞上障碍物,就视为任务失败。

在赛车的马力和灵活性等性能相差较小的情况下,要控制速度极快的赛车绕开障碍物移动到终点,关键是提高选手的反应灵敏度,即两次改变赛车运动方向所间隔的最短时间,也可称为选手的反应时间。使自己能够更快地控制赛车改变前进的方向。

当然,由于选手反应灵敏度的不同,可选择的路径就会大不相同。如图 11 和图 22 所示,对于同一个赛场,两位选手的反应时间分别为 22 秒和 11 秒,而其到达终点所需的时间分别为 1818 秒和 1616 秒(赛车每秒可沿当前方向移动一格,从起点出发时算改变一次方向)。

由图 11 和图 22 可知,赛车的最短路线长度是由选手的反应灵敏度所决定的,当选手的反应很慢时,可能就不会存在可行的路径。你的任务是:在能够完成赛程(即存在从起点到终点的路径)的条件下,求出选手每个可能的反应时间所对应的最短路线长度。

输入格式

第一行包含两个整数 NNMM,表示赛场的行数和列数。1N,M1001≤N, M≤100

第二行有四个整数 x1x1y1y1x2x2y2y2,表示赛程的起点和终点的位置分别为 (x1,y1(x1, y1x2,y2x2,y2

接下来 NN 行是一个 N×MN×M 的 0-1 矩阵,矩阵中第 ii 行第 jj 列元素 Ai,j=1A_{i,j}=1 表示赛场中位置 (i,j)(i,j) 为赛道,Ai,j=0A_{i,j}=0 表示赛场中位置 (i,j)(i,j) 有障碍物。

输出格式

输出文件可能有多行,其中每行输出一个可能的选手反应时间及该时间所对应的最短路线长度。输出文件中必须包含所有符合题目要求的选手反应时间。注意:由于选手的反应时间不可能很慢,因而不必考虑选手反应时间大于 1010 秒的情况,只需输出 1010 以内(包含 1010)的解。

10 10                                   
1 4 10 7                                 
0 0 0 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 0 1 0 0 0 0
1 1 1 1 0 1 1 1 1 0
1 0 0 0 0 0 0 0 1 0
1 0 1 1 1 0 1 1 1 0
1 1 1 0 1 1 1 0 1 0
0 0 1 0 0 0 0 0 1 0
0 0 1 1 1 1 1 1 1 0
0 0 0 0 0 0 1 0 0 0

1 16
2 18