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

*【递归】最少转弯问题

【题意】

某士兵被困在一个 n×mn \times m 的雷区中,他需要从起点(x1,y1)(x_1,y_1)走到终点(x2,y2)(x_2,y_2)

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

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

【输入数据】

输入数据共若干行。

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

下来 nn 行,每行mm010表示安全,1表示地雷)。

下来一行四个整数 x1 y1 x2 y2x_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

【输出样例】

5