欢迎来到广度优先的世界
广度优先算法(Breadth-First Search),同广度优先搜索,又称作宽度优先搜索,或横向优先搜索,简称BFS
风和日丽的一天,一位叫小明的同学被困在了迷宫里,现在你在迷宫的左上角,你希望用最短的路径把他救出来,你会怎么做?
由于我们不知道小明的位置,所以只能一条一条的试,我们可以从上下左右走,而每到一个地方也可以上下左右走,但是绝不走重复路也不碰到墙壁,就像下面这张图
这样,只要我们不被迷宫困住,就一定可以找到小明
那么我们该如何实现广度优先呢?
这里我们先来认识一种数据结构:队列
队列的特性是先进先出(比如说在排队时(没人插队),最先进入队伍的最先出去),我们发现,广度优先恰恰也可以用先进先出的方式实现
可以先把第一个坐标加入队列,遍历上下左右4个方向,如果我可以到达,就把它压入队列
然后while(!q.empty()),只要队列不空,那就继续遍历
这里解释一下STL里队列里的成员函数:
queue <int> q;//创建一个变量名为q,类型为int的队列,注意,类型可以是结构体等等
q.empty()//返回值为true或false,表示队列是否为空
q.size()//队列里还有的元素数量
q.front()//返回队头
q.pop()//压出队头
q.push(x)//压入x
最后,请大家尝试用所学的知识完成:#252. Lake Counting,相信聪明的你一定能做出来