广度优先搜索 (BFS)

基本操作：

第一：找到状态储存方式：struct（x,y,steps） 和 访问过的状态标记 vis[x][y]

第二：创建队列，将首个状态加入到队列中

第三：取q.front()；找到转移方程 （x+1,y,z,steps） 并且检查标记vis

是→不操作

否→加入到队列中 vis标记为1

例题如下

例题 1

随着时间的推移，这一题目描述图片走失了

使用BFS，状态所在层数level和已经经过的按钮次数steps（level，steps）

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
 
struct node{
    int level;
    int steps;
    node(int level,int steps):level(level),steps(steps){}
};
 
queue<node> q;
bool vis[220];
int k[220];
 
int bfs(int s,int e,int n){
    node cur=node(s,0);
    vis[s]=1;
    q.push(cur);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        if(cur.level==e){
            return cur.steps;
        }
        if(cur.level+k[cur.level ]<=n){
            if(!vis[cur.level+k[cur.level ]]){
                vis[cur.level]=1;
                q.push(node(cur.level+k[cur.level],cur.steps+1));
            }
        }
        if(cur.level-k[cur.level ]>=1){
            if(!vis[cur.level-k[cur.level ]]){
                vis[cur.level]=1;
                q.push(node(cur.level-k[cur.level],cur.steps+1));
            }
        }
    }
    return -1;
}
 
int main(){
    int n=0;
    while(scanf("%d",&n),n){
        for(int i=0;i<=n;i++){
            k[i]=0;
            vis[i]=0;
        }
        int s,e;
        cin>>s>>e;
        for(int i=1;i<=n;i++){
            scanf("%d",&k[i]);
        }
        printf("%d\n",bfs(s,e,n));
    }
    return 0;
}

例题 2

题目描述：

每当刘一丁买了可乐，刘二丁就要求和和他一起分享，而且一定要喝的和刘一丁一样多。但刘一丁的手中只有两个杯子，它们的容量分别是N和M毫升，可乐的体积为S（S<101）毫升（正好装满一瓶），它们三个之间可以相互倒可乐（都是没有刻度的，且 S==N+M, 101>S>0, N>0, M>0）。

如果能平分，请输出倒可乐的最少次数，如果不能，请输出”NO”。

Input | Output 7 4 3 | NO 4 1 3 | 3 0 0 0

BFS优先队列默认大顶堆 本质是堆 优化