TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3630
  • Problem
  • P3630最少转弯问题
    Limits : Time Limit : 10000 MS   Memory Limit : 615536 KB
    Description

    给出一张地图,这张地图被分为n*m(n,m<=100)个方块,任何一个方块不是平地就是高山。平地可以通过,高山则不能。
    现在你处在地图的(x1,y1)这块平地,问:你至少需要转几个弯才能到达目的地(x2,y2)?你只能沿着水平和垂直方向的平地上行进,转弯次数就等于行进方向的改变(从水平到垂直或从垂直到水平)的次数

    Input Format

    第一行为n和m
    接下来一个n*m的矩阵,表示地图,其中数字0表示空地,1表示高山,数字间以空格间隔。
    最后一行,四个整数,表示x1,y1,x2,y2

    Output Format

    输出最少转弯次数

    Sample Input 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

    Sample Output 1

    5

    Sample Input 2

    10 15
    1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 
    1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 
    1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 
    1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
    0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 
    1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 
    0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 
    1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 
    0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 
    2 15 5 9 

    Sample Output 2

    2

    Hint

    样例说明,路线如下图所示


    Source  感谢zmy和lym发现问题并提供正确数据