关于BFS的拓展（1）——多源BFS，最小步数，双端队列
矩阵距离（多源BFS）
题意：
给定一个01矩阵，求每个位置到所有1的最短曼哈顿距离。
思路：
朴素的做法是分别以每个1为起点遍历一遍，最后保留最小值，时间复杂度O（n^2）。
在图论里，如果求所有点到最近起点的最短距离，可以建立一个虚拟源点，从虚拟源点往每个起点连一条边权为0的边，这时候再求一遍最短路即可。
借鉴上述思想，我们可以只需要把所有起点的距离都初始化为0，再把所有起点都放入队列里，这样就可以求得到最近起点的最短距离。
关于该题的读入，可以使用字符串读入，也可以使用代码里的%1d读入。
魔板（最小步数）
题意：
给出3种操作和初始数列，问最少经过几次操作后可以得到结束状态。
思路：
是把每一个状态看做是有向图上一个点，在这个有向图上求最短距离。
基本的思路就是将初始状态放入队列，然后按照ABC的操作顺序对该状态进行操作后并且放入队列中，看该状态是否跟结束状态一样。
关键在于如何存储状态，一般是用哈希来存，也可以用康拓展开，也可以用map来存。
记录方案就是存一下每个状态由哪一个状态转移过来，这样就可以由终点倒推到起点。
至于如果保证最终的字典序最小，可以在操作的时候按照ABC的操作顺序进行操作，并且加入队列里，具体的证明可以看这篇博客里的注释。
双端队列BFS
做过一次UPC的G，感觉比电路维修更好入门。
只含有0和1两种权值的最短路问题，可以用双端队列来做。
判断扩展出的边的权值。如果是0，则插到队头；如果是1，则插到队尾。
证明，其实也可以看算法竞赛进阶指南书里的证明。
投递网易等公司10个岗位 >