A292.最少转弯问题
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给出一张地图,这张地图被分为 n×m (1≤n,m≤100) 个方块,任何一个方块不是平地就是高山。平地可以通过,高山则不能。
现在你处在地图的 (x1,y1) 这块平地,问:你至少需要拐几个弯才能到达目的地 (x2,y2)?
其中,你只能沿着水平和垂直方向的平地上行进,拐弯次数就等于行进方向的改变(从水平到垂直或从垂直到水平)的次数。
输入格式
第一行输入两个整数 n,m,代表一个高为 n,宽为 m 的地图。
接下来读入一整个地图,共有 n 行,每行有 m 列。其中,0 表示空地,1 表示高山。
最后一行读入四个整数,x1,y1,x2,y2,代表出发点坐标和终点坐标。保证出发坐标和终点坐标一定是平地。
输出格式
输出一个整数 ans,代表到达坐标 (x2,y2) 最小的转弯次数。如果无法到达目标地点,则输出 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≤n,m≤100。
对于100%的数据,保证 x1,x2∈[1,n]∩N+ 且 y1,y2∈[1,m]∩N+。
本题测试点分布如下:
题目编号 | 数据范围 |
---|---|
1-10 | 1≤n,m≤15 |
11-25 | n=20,m=20 |
26-50 | 80≤n,m≤100 |
样例描述:
对于第一个样例,一个可行的方案如下图所示。其中红色表示高山,蓝色表示平地。为了前往终点 (1,7),我们需要分别在坐标 (1,4),(4,4),(4,6),(2,6),(2,7) 处转弯,转弯次数共五次。故答案为 5。
对于第二个样例,不存在一个可行的方案。