A292.最少转弯问题

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

现在你处在地图的 (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

说明/提示

对于所有数据,1≤n,m≤1001\le n,m\le100,1≤x1,x2≤n1\le x_1,x_2\le n,1≤y1,y2≤m1\le y_1,y_2\le m。

本题测试点分布如下:

测试点编号 nn mm
1~10 1≤n≤151\le n\le15 1≤m≤151\le m\le15
11~25 n=20n=20 m=20m=20
26~50 80≤n≤10080\le n\le100 80≤m≤10080\le m\le100

样例描述:

对于第一个样例,一个可行的方案如下图所示。其中红色表示高山,蓝色表示平地。为了前往终点 (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。

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

输入解题思路,AI测评打分。不知道怎么写?

首页