一道很经典的 BFS 题
想认真的写篇题解。
题目来自：https://www.luogu.org/problemnew/show/P1126
题目描述机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N×M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入第一行为两个正整数N,M(N,M≤50)，下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有4个整数和1个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
图例以前在刷刘汝佳的紫书《算法竞赛入门经典》时做过这道题，现在又再次遇到，幸不汝（辱）命，一次就过了。
BFS 性质我们都知道，BFS 具有从起点到目标节点（或状态）路径最短的特性，但是使用 BSF 这一特性时需要注意，只有当所有的边权重相同（一般为1）时，它才具有此性质，边权不等时不具有。BFS 每次从一个节点只经历一次转移，当求单纯的求距离时可以认为每次转移的边权为一，转移次数最少的路径一定是距离最短的。我们可以用两张图来直观的表现这个特性：
在图上：
初始节点为 0，每次从一个节点向四周节点扩散，访问所有距离为一（相邻，经过一次状态转换）的节点。
第一次扩散访问了所有蓝色节点，并没有找到目标节点，继续扩散。第二次扩散访问了两个粉色节点，虚线节点并没有被访问。因为在扩散到左边的粉色节点时，我们已经找到了目标节点。那么不去搜索第三个粉色节点（虚线）节点不会丢解吗？在图中我们也确实能看到，虚线节点在经历一次扩散后，到达紫色节点，紫色节点再扩散一次，也可到达目标节点。不过，这个选择无论是从上述图片还是从我的描述文字来看，他的距离都不短。那么为什么会这样呢？我说一下我个人的理解。看下面一幅图：
在树上：
在树上的 BFS 被称为层次遍历。他的工作原理就如其名，每次访问一层的节点，同一层的节点有一个特点就是，他们的层数是相同的，也即到根节点的距离。当扩散到第三层时，（从左向右）第三个粉色节点作为目标节点被发现，此时我们可以对比三种情况：
由于第三个粉色节点为第一个目标节点，所以所有该节点左侧同层节点都不是目标节点，并且从这些节点继续扩散出的节点的层数（即到根节点的距离）一定 大于 第三个粉色节点到根节点的距离。
对于第三个粉色节点，也即我们的第一个目标节点（为什么强调 “第一个” 因为可能有不止一个目标节点，即多个解），由他扩散而出的子节点的距离一定 大于 这个节点。
对于虚线节点，由于他是不是目标节点，在未访问到时未知，而他的性质是和第一种情况相似的，所以去访问并扩散虚线节点我们能得到的结果是他的距离
大于等于 第三个粉色节点
由此，可以得出如果只有一个解，那么第一次被发现的目标节点 即第三个粉色节点一定是距离根节点最近的。
在图上也可以类比层的概念，得出相同的结论。
解题思路BFS 的性质讨论完，再来具体考虑这道题。这道题应该能明显看出来，是在图上寻找最短路的问题。不过首先需要对数据进行一些分析处理，才能更好的应用 BFS。此题唯一有些麻烦的就是，机器人具有半径，将每个格子单独处理不方便。由给出的图例可以发现，机器人一定会占据四个格子的空间，而一旦一个格子障碍物出现，那么这个障碍物格子所在的四个四方格上的中心格点机器人都不能走（机器人只走格点）。