Problem P: 29-搜索练习-最少转弯问题

Problem P: 29-搜索练习-最少转弯问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

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


Input

输入有多组数据，每组数据的第一行为n和m，第2至n+1行为整个地图地形描述(0:空地;1:高山)，第n+2行为起点坐标x1,y1,终点坐标x2,y2。


Output

对于每组数据输出最少转弯次数。

Sample Input

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

5

[Submit][Status]