T. *【递归】最少转弯问题

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

某士兵被困在一个 $n \times m$ 的雷区中，他需要从起点 $(x_1,y_1)$ 走到终点 $(x_2,y_2)$ 。

在行走过程中，他只能沿水平方向或垂直方向行走，且不能走到有地雷的地方。

为了避免头晕，现请你帮他设计一条线路，使用最少的转弯次数，从起点走到终点。

输入数据共若干行。

第一行两个整数 $n \ m \ (3 \le n,m \le 100)$ 。

下来 $n$ 行，每行 $m$ 个0或1（0表示安全，1表示地雷）。

下来一行四个整数 $x_1 \ y_1 \ x_2 \ y_2$ ，表示起点和终点的位置。

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