A4453. 【搜索】【广度优先】最短路径的转弯数
编程题
普及-
知识点
题目描述
给定一个 $N\times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 从起点坐标到终点坐标的最短路径上有多少个转弯（保证只有一条最短路径）。
输入格式
第 $1$ 行：$n$ $m$
第 $2$ 至 $n+1$ 行：整个迷宫描述（$0$：可走；$1$：不可走），
比如：
第 $2$ 行迷宫描述为：
第 $3$ 行迷宫描述为：
$\cdots$
第 $n+2$ 行：
第 $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
3