曹文信息在线OJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
5593: 最少转弯问题
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:12
Solved:12
Submit
Submit Record
Statistics
Web Board
ShowOff!
Description
给出一张地图,这张地图被分为
n
×
m
(
n,m<=100
)个方块,任何一个方块不是平地就是高山。平地可以通过,高山则不能。现在你处在地图的(
x1,y1
)这块平地,问:你至少需要拐几个弯才能到达目的地(
x2,y2
)?你只能沿着水平和垂直方向的平地上行进,拐弯次数就等于行进方向的改变(从水平到垂直或从垂直到水平)的次数。例如:如图
1
,最少的拐弯次数为
5
。
Input
第
1
行:
n m
第
2
至
n+1
行:整个地图地形描述(
0
:空地;
1
:高山),
如(图
1
)第
2
行地形描述为:
1 0 0 0 0 1 0
第
3
行地形描述为:
0 0 1 0 1 0 0
……
第
n+2
行:
x1 y1 x2 y2
(分别为起点、终点坐标)
Output
s (即最少的拐弯次数)
Sample Input
Copy
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
Copy
5
Source/Category
宽搜