P2114 - 【2018冬令营】最少转弯问题

Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs

Memory Limit：128 MB Time Limit：1.000 S

Judge Style：Text Compare Creator：

Submit：97 Solved：16

某士兵被困在一个n*m的雷区中，他需要从起点(x1,y1)走到终点(x2,y2)。在行走过程中，他只能沿水平方向或垂直方向行走，且不能走到有地雷的地方。为了避免头晕，现请你帮他设计一条线路，使用最少的转弯次数，从起点走到终点。

输入共若干行。第一行包含两个整数n和m（3<=n,m<=100）。从第2行到第n+1行，每行m个0或1（0表示安全，1表示地雷）。第n+2行，包含四个整数x1, y1, x2, y2，表示起点和终点的位置。

输出数据仅一个整数，表示所需最少转弯次数。无法到达终点时输出“-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

宽搜高级B

2114: 【2018冬令营】最少转弯问题