← 返回比赛
已结束 GESP挑战赛#35
← 上一题 下一题 →

A7515 | 隔墙穿行

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

$Sherry$ 来到了一座特殊迷宫。迷宫可以看成一个 $n$ 行 $m$ 列的矩阵，每个位置用数字表示：

- $0$ 表示空地，可以正常进入；
- $1$ 表示墙壁，不能正常进入。

$Sherry$ 一开始站在起点 $(s_x,s_y)$，她希望到达终点 $(t_x,t_y)$。保证起点和终点都是空地。

每一步，$Sherry$ 可以选择向上、下、左、右中的一个方向行动。

如果相邻位置是空地，她可以正常走到该位置。

如果相邻位置是墙壁，$Sherry$ 可以使用穿墙能力，直接穿过这堵墙，到达墙另一侧的位置。穿墙算作一步移动。

不过，穿墙需要满足以下条件：

- 上一步不能也是穿墙；
- 相邻位置必须是墙壁；
- 墙另一侧必须仍在迷宫内；
- 墙另一侧必须是空地。

请你计算，$Sherry$ 从起点到终点最少需要多少步。如果无法到达终点，输出 $-1$。

输入格式

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

接下来 $n$ 行，每行 $m$ 个整数，表示迷宫。

最后一行输入四个整数 $s_x,s_y,t_x,t_y$，分别表示起点和终点的位置。

输出格式

输出一个整数，表示从起点到终点的最少步数。

如果无法到达终点，输出 $-1$。

输入输出样例

输入 #1
5 5
0 0 1 0 0
1 0 1 0 1
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
1 1 1 5
输出 #1
3
输入 #2
3 5
0 1 0 1 0
1 1 1 1 1
0 1 0 1 0
1 1 1 5
输出 #2
-1
C++ 编辑器
输入
输出