最少转弯问题 士兵被困
测试数据来自 wjszez/2104
作业已超过截止时间,您无法递交本题目。
【问题描述】
某士兵被困在一个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
输出样例:
5