题解

​ BFS 的经典题，如果之前写过 BFS 走迷宫的同学，这题应该可以轻松 AC。

走迷宫具体做法如下

​ 从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往外扩展一层，这是第二步。

记录下所有第二步能走到的点，重复下去，直到走到终点。输出步数即可。

问题描述

在一个 $n$ 行 $m$ 列的网格城市中，配送员小红需要从起点 $A$ 前往取餐点 $B$，再将餐食送至客户处 $C$。网格中的部分格子是不可通行的。小红每次移动可以从一个可通行的格子走到另一个相邻的可通行格子。已知小红的起点坐标为 $(X_A, Y_A)$，取餐点坐标为 $(X_B, Y_B)$，客户处坐标为 $(X_C, Y_C)$。请计算小红完成配送任务至少需要移动多少步。

输入格式

第一行包含两个正整数 $n, m$，表示网格城市的行数和列数。
接下来 $n$ 行，每行包含 $m$ 个字符，表示网格图。其中 # 表示不可通行的格子，. 表示可通行的格子。
最后一行包含六个正整数 $X_A, Y_A, X_B, Y_B, X_C, Y_C$，表示起点、取餐点和客户处的坐标。

输出格式

输出一个整数，表示小红完成配送任务的最少移动步数。

样例输入

7 8
........
.#.#####
.#...#..
.#.#.#.#
.#.#....
##.###.#
.....#..
5 1 1 7 2 3

样例输出

15

评测数据与规模

对于所有评测数据，满足 $1 \leq X_A, X_B, X_C \leq n$ 且 $1 \leq Y_A, Y_B, Y_C \leq m$，$1 \leq n, m \leq 1000$。保证起点、取餐点和客户处的坐标位于可通行的格子上，并且至少存在一条合法的路径连接这三点。