#€. 【提高】最小拐弯路径

    Type: Default 1000ms 128MiB

【提高】最小拐弯路径

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

农夫约翰在农场工作了一天,感觉比较累,准备开车回家。约翰在比较累的时候,喜欢走直路,不喜欢拐弯,哪怕走少拐弯的路回家更远,约翰也想走直路(好任性的约翰!)。请你从约翰的出发地到目的地找一条路,使得约翰回家拐弯数量最少。

输入格式

第一行两个整数n和m(n和m都是1000以内的整数),代表地图的大小。
接下来的n行,每行有m个数,其中能够同行的点用0表示,不能通行的点用1表示。
再接下来1行,有4个整数,s1、s2、e1、e2,s1和s2表示出发点的坐标,e1和e2表示目的地的坐标。

输出格式

约翰从出发点到目的地最少要拐弯的数量,本题所有数据都确认从出发点到目的地是有路径可达的。

样例

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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45