TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • 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发现问题并提供正确数据