← 返回题目
题库练习 最少转弯问题
← 上一题 下一题 →

A381 | 最少转弯问题

来源官方 / 2022
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给出一张地图，这张地图被分为 $n\times m \space (1 \le n, m \le100)$ 个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。

现在你处在地图的 $(x_1, y_1)$ 这块平地，**问：你至少需要拐几个弯才能到达目的地 $(x_2, y_2)$？**

其中，你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。

输入格式

第一行输入两个整数 $n, m$，代表一个高为 $n$，宽为 $m$ 的地图。
接下来读入一整个地图，共有 $n$ 行，每行有 $m$ 列。其中，$0$ 表示空地，$1$ 表示高山。
最后一行读入四个整数，$x_1, y_1, x_2, y_2$，代表出发点坐标和终点坐标。保证出发坐标和终点坐标一定是平地。

输出格式

输出一个整数 $ans$，代表到达坐标 $(x_2, y_2)$ 最小的转弯次数。如果无法到达目标地点，则输出 Unattainable (大小写敏感)。

输入输出样例

输入 #1
5 7
1 0 0 0 0 1 0 
0 0 1 0 1 0 0 
0 0 0 0 1 0 1 
0 1 1 0 0 0 0 
0 0 0 0 1 1 0
1 3 1 7
输出 #1
5
输入 #2
1 5
0 0 0 1 0
1 1 1 5
输出 #2
Unattainable
输入 #3
5 5
0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
1 1 5 5
输出 #3
4
C++ 编辑器
输入
输出