问题描述

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

题解

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

走迷宫具体做法如下

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

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