P3630 - 最少转弯问题

Problem

P3630最少转弯问题

Limits : Time Limit : 10000 MS Memory Limit : 615536 KB

Description

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

Input Format

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

Output Format

输出最少转弯次数

Sample Input 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

Sample Output 1

Sample Input 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

Sample Output 2

Hint

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

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