做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2313. -- [C++一本通-广度优先搜索]3.最少转弯问题

2313: [C++一本通-广度优先搜索]3.最少转弯问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 259  解决: 91
[上一题][提交][讨论版][状态][下一题]

题目描述

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

                                                  

输入

第1行: n   m

第2至n+1行:整个地图地形描述(0:空地;1:高山)

第2行地形描述为:1 0 0 0 0 1 0

第3行地形描述为:0 0 1 0 1 0 0

……

第n+2行:x1    y1   x2  y2(分别为起点、终点坐标)

输出

s(即最少的拐弯次数)

样例输入

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

样例输出

5

提示

标签

[上一题][提交][讨论版][状态][下一题]