宽度优先搜索

又有的时候，我们还会碰到这样一些貌似可以用深搜解决，但又有点茫然打不出深搜程序的题：奇怪的电梯、倒牛奶、面积……这些问题，问的都是最怎么怎么样，但也是从一个起点出发往下走。怎么办？这时候我们就要用到一个新的算法。虽然也叫搜索，但它并没有回溯这个操作。它和深度优先搜索一样，有个昵称：广度优先搜索。当然了，它肯定有个正式名称，那就是

宽度优先搜索（BFS，简称宽搜）

那么，宽度优先搜索又是个什么东西？它和深度优先搜索又有什么区别？我会在这里一一介绍。

一、宽度优先搜索的思想

宽度优先搜索是从一个节点（位置）出发，拓展出所有它可以拓展出来的节点（位置）。接着，指针移到下一个位置，对这个位置继续进行拓展，然后指针再移到下一个位置，再继续拓展……直到找到答案为止。

它和深度优先搜索不同，深度优先搜索是“往死里走”，宽度优先搜索则是不紧不慢地，先拓展完一个再拓展另一个。

二、宽度优先搜索的基本用途

宽度优先搜索一般在“最值问题”中会大显身手，当然在总的方案问题中也占有一席之地（当深搜会爆栈时）。在图论问题中，它也经常用来遍历一个图；树的遍历，有时也会用来完成。

三、宽度优先搜索的写法

与深搜不同，宽搜一般用while循环来实现。宽度优先搜索其实相当于创建一个队列（或者说填充数组），要用两个指针i，j。i表示当前正在拓展的节点（位置），j表示这个数组的终点。

以下是宽度优先搜索的框架：

初始化data、i=0、j=1和标记（凡是搜索都离不开标记这个玩意儿，一定要记住！不然Runtime Error或者Time Limit Exceeded别怪我没说过！）
while(i
    i++;
    for(int s=1;s
        j++;
        拓展新节点；记录步数；标记；
        if(新节点==目标节点) printf步数，退出；（如果是求总的方案，则ans++）
    }
}