A381. 最少转弯问题
编程题
普及/提高-
知识点
题目描述
给出一张地图，这张地图被分为 $n\times m \space (1 \le n, m \le100)$ 个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。
现在你处在地图的 $(x_1, y_1)$ 这块平地，**问：你至少需要拐几个弯才能到达目的地 $(x_2, y_2)$？**
其中，你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。
现在你处在地图的 $(x_1, y_1)$ 这块平地，**问：你至少需要拐几个弯才能到达目的地 $(x_2, y_2)$？**
其中，你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。
输入格式
第一行输入两个整数 $n, m$，代表一个高为 $n$，宽为 $m$ 的地图。
接下来读入一整个地图，共有 $n$ 行，每行有 $m$ 列。其中，$0$ 表示空地，$1$ 表示高山。
最后一行读入四个整数，$x_1, y_1, x_2, y_2$，代表出发点坐标和终点坐标。保证出发坐标和终点坐标一定是平地。
接下来读入一整个地图，共有 $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
说明/提示
本题数据和题面均已更新，不存在测试点数据错误的情况。
**数据范围与约定：**
对于100%的数据，保证 $1 \le n, m \le100$。
对于100%的数据，保证 $x_1, x_2 \in [1, n] \cap \N_+$ 且 $y_1, y_2 \in [1, m] \cap \N_+$。
**本题测试点分布如下：**
| 题目编号 | 数据范围 |
|:--:|:--:|
| 1-10 | $1 \le n, m \le 15$ |
| 11-25 | $n = 20, m = 20$ |
| 26-50 | $80 \le n, m \le 100$ |
**样例描述：**
对于第一个样例，一个可行的方案如下图所示。其中红色表示高山，蓝色表示平地。为了前往终点 $(1, 7)$，我们需要分别在坐标 $(1, 4), (4, 4), (4, 6), (2, 6), (2, 7)$ 处转弯，转弯次数共五次。故答案为 $5$。
对于第二个样例，不存在一个可行的方案。
**数据范围与约定：**
对于100%的数据，保证 $1 \le n, m \le100$。
对于100%的数据，保证 $x_1, x_2 \in [1, n] \cap \N_+$ 且 $y_1, y_2 \in [1, m] \cap \N_+$。
**本题测试点分布如下：**
| 题目编号 | 数据范围 |
|:--:|:--:|
| 1-10 | $1 \le n, m \le 15$ |
| 11-25 | $n = 20, m = 20$ |
| 26-50 | $80 \le n, m \le 100$ |
**样例描述：**
对于第一个样例，一个可行的方案如下图所示。其中红色表示高山，蓝色表示平地。为了前往终点 $(1, 7)$，我们需要分别在坐标 $(1, 4), (4, 4), (4, 6), (2, 6), (2, 7)$ 处转弯，转弯次数共五次。故答案为 $5$。
对于第二个样例，不存在一个可行的方案。