*L5攻防游戏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小明在玩一个迷宫冒险游戏,迷宫地图可以用一个n*m的二维矩阵表示(左上角元素坐标是第1行,第1列)。他手里有一个引爆装置,只要将这个引爆装置放置在指定的两个目标点中的任意一个位置就能获胜,迷宫里有很多炸弹,他根据情报得到了这个迷宫里所有炸弹的位置。他需要安全来到任意一个目标店,但只能在没有炸弹的格子间上下左右移动。给定小名的初始位置,请计算去那个目标点路径最短,最短的路径有多长。

例如:n=3,m=3,迷宫地图如下所示:

(1,2)位置为小名的初始位置,(3,2)和(3,3)位置为两个目标点,其中(3,2)位置距离起点最近,路径为(1,2)->(2,2)->(3,2),路径长度为2。

Format

Input

第一行包含两个整数n,m,表示地图的大小。 接下来n行每行包含m个数字,数字只能是0或1,1表示炸弹,0表示没有炸弹,数字之间不需要隔开; 借来下一行包含两个整数x,y,表示小明当前位置的坐标,整数之间一个空格隔开; 接下来一行包含四个整数x1,y1,x2,y2,表示两个目标店坐标,整数之间以一个空格隔开。 数据保证到达两个目标点的路径长度不同。

数据范围: 测试点1~10:1<=n,m<=100,1<=x1,x2<=n,1<=y1,y2<=m。

Output

如果能安全到达其中一个目标点,就输出两行。 第一行包含两个整数,表示路径最短的目标点坐标,整数之间以一个空格隔开。 第二行是一个整数,表示这个最短的路径。 如果两个目标店都无法安全到达,就输出“No Result”。

Samples

3 3
001
100
000
1 2
3 2 3 3
3 2
2
3 5
01000
10110
10001
3 2
1 1 1 3
No Result

Limitation

1s, 256MB for each test case.

2025春学期第1-3次课0308

未参加
状态
已结束
规则
IOI
题目
35
开始于
2025-2-22 8:30
结束于
2025-3-11 0:30
持续时间
400 小时
主持人
参赛人数
25