A4453 | $【搜索】【广度优先】最短路径的转弯数$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个 $N\times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 从起点坐标到终点坐标的最短路径上有多少个转弯（保证只有一条最短路径）。

第 $1$ 行：$n$ $m$ 第 $2$ 至 $n+1$ 行：整个迷宫描述（$0$：可走；$1$：不可走）， 比如： 第 $2$ 行迷宫描述为：1 0 0 0 0 1 0 第 $3$ 行迷宫描述为：0 0 1 0 1 0 0 $\cdots$ 第 $n+2$ 行：x1 y1 x2 y2 （分别为起点、终点坐标）

$s$ （即最短路径的拐弯次数）

输入 #1

5 7
0 0 0 1 1 1 1
0 1 0 1 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
1 2 5 7

输出 #1

C++ 编辑器

输入

输出