TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  課程の中心  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3630
  • 問題
  • P3630最少转弯问题
    制限 : 時間制限 : 10000 MS   メモリ制限 : 615536 KB
    問題説明

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

    入力形式

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

    出力形式

    输出最少转弯次数

    サンプル入力 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

    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 

    サンプル出力 2

    2

    ヒント

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


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