A292.最少转弯问题

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

现在你处在地图的 (x1,y1)(x_1, y_1) 这块平地,问:你至少需要拐几个弯才能到达目的地 (x2,y2)(x_2, y_2)

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

输入格式

第一行输入两个整数 n,mn, m,代表一个高为 nn,宽为 mm 的地图。
接下来读入一整个地图,共有 nn 行,每行有 mm 列。其中,00 表示空地,11 表示高山。
最后一行读入四个整数,x1,y1,x2,y2x_1, y_1, x_2, y_2,代表出发点坐标和终点坐标。保证出发坐标和终点坐标一定是平地。

输出格式

输出一个整数 ansans,代表到达坐标 (x2,y2)(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%的数据,保证 1n,m1001 \le n, m \le100
对于100%的数据,保证 x1,x2[1,n]N+x_1, x_2 \in [1, n] \cap \N_+y1,y2[1,m]N+y_1, y_2 \in [1, m] \cap \N_+

本题测试点分布如下:

题目编号 数据范围
1-10 1n,m151 \le n, m \le 15
11-25 n=20,m=20n = 20, m = 20
26-50 80n,m10080 \le n, m \le 100

样例描述:

对于第一个样例,一个可行的方案如下图所示。其中红色表示高山,蓝色表示平地。为了前往终点 (1,7)(1, 7),我们需要分别在坐标 (1,4),(4,4),(4,6),(2,6),(2,7)(1, 4), (4, 4), (4, 6), (2, 6), (2, 7) 处转弯,转弯次数共五次。故答案为 55

对于第二个样例,不存在一个可行的方案。

首页