算法总结—BFS

· · 算法·理论

1.\ \text{Lucky Numbers}

这道题深搜和广搜都能写出来，而且时间复杂度相差不多，因为这题的数据范围太小了。

我们在广搜时只需要枚举是把 4 接在后面还是把 7 接在后面，就可以了。记得在搜索时用两个变量来记录此时数字中 4 和 7 的数量，这样就不用算出一个数字统计一遍了。

DFS 代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n;
int cnt1=0;
int ans=0;
int Min=1e18;
void dfs(int cnt,int cnt1,int cnt1){
    string s=to_string(cnt);
    if(s.size()>10){
        return;
    }
    if(cnt1==cnt1&&cnt>=n){
        if(Min>cnt-n){
            Min=cnt-n;
            ans=cnt;
        }
    }
    dfs(cnt*10+4,cnt1+1,cnt2);
    dfs(cnt*10+7,cnt1,cnt2+1);
}
signed main(){
    cin>>n;
    dfs(0,0,0);
    cout<<ans;
    return 0;
}

BFS 代码

#include<iostream>
#include<queue>
#define int long long
using namespace std;
struct node{
    int x;
    int cnt1,cnt2;
};
queue<node>q;
signed main(){
    int n;
    cin>>n;
    q.push({0,0,0});
    while(q.size()){
        node t=q.front();
        q.pop();
        if(t.x>=n&&t.cnt1==t.cnt2){
            cout<<t.x;
            return 0;
        }
        q.push({t.x*10+4,t.cnt1+1,t.cnt2});
        q.push({t.x*10+7,t.cnt1,t.cnt2+1});
    }
    return 0;
}

2.\ \text{Water The Garden}

这是一道多源点一维广搜，我们把每个水龙头的位置都放入队列里，并标记，然后往前往后扩展，直到全部被水占领。

多组数据记得清空!

代码

#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
int a[205];
struct node{
    int x;
    int step;
};
queue<node>q;
bool vis[205];
int dx[3]={-1,1};
int Max=-1e9;
void work(){
    while(q.size()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    Max=-1e9;
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        q.push({a[i],1});
        vis[a[i]]=1;
        cnt++;
    }
    if(cnt==n){
        cout<<1<<endl;
        return;
    }
    while(q.size()){
        node t=q.front();
        q.pop();
        for(int i=0;i<2;i++){
            int tx=t.x+dx[i];
            if(tx<1||tx>n||vis[tx]==1){
                continue;
            }
            q.push({tx,t.step+1});
            vis[tx]=1;
            Max=max(Max,t.step+1);//记录最大值，如果全部铺满了，就不会搜到这里
        }
    }
    cout<<Max<<endl;
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}

3.\ \text{Required Length}

就用 BFS 去搜，每次 x 是乘上多少，不过题目中有一个特殊要求，乘的数一定是包含在数本身中的，所以每次 BFS 向外扩展时，还需要用一个桶做标记。

本题数据达到了 10^{18}-1 所以标记时得用 \text{map}

代码

#include<iostream>
#include<map>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
struct node{
    int x;
    int step;
};
queue<node>q;
map<long long,bool>vis;
bool tong[10];
int len(int x){
    if(!x){
        return 1; 
    }
    int t=x;
    int cnt=0;
    while(t){
        cnt++;
        t/=10;
    }
    return cnt;
}
signed main(){
    int n,x;
    cin>>n>>x;
    q.push({x,0});
    vis[x]=1;
    if(x==1){ 
        cout<<-1;
        return 0;
    }
    while(q.size()){
        node t=q.front();
        q.pop();
        memset(tong,0,sizeof(tong));
        int k=t.x;
        while(k){//统计乘数中包含了哪些数
            tong[k%10]=1;
            k/=10;
        }
        for(int i=2;i<=9;i++){//不能乘1或者0否则会死循环
            if(tong[i]==0){
                continue;
            }
            int tx=t.x*i;
            if(tx<1||tx>9e18||vis[tx]){
                continue;
            }
            if(len(tx)>n){
                continue;
            }
            q.push({tx,t.step+1});
            vis[tx]=1;
            if(len(tx)==n){
                cout<<t.step+1;
                return 0;
            } 
        }
    }
        cout<<-1;
    return 0;
}

4.\ 倒水问题

这道题就是在 BFS 中模拟 6 个操作，再用一个字符串来储存答案。

注意这题的 vis 标记的是两个杯子中的水量，如果一种水量被标记过了，就意味则遇到了相同的情况，后面的操作都一模一样，而且还没有第一次那么优。

代码

#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
struct node{
    int x,y;
    string s;
    int step;
};
queue<node>q;
bool vis[1005][1005];
int a,b,n;
void bfs(){
    q.push({0,0,"",0});
    vis[0][0]=1;
    while(q.size()){
        node t=q.front();
        q.pop();
        if(t.y==n){
            cout<<t.s.size()/2<<t.s;//由于t.s中包含空格，所以t.size() 要除以2
            cout<<endl;
            return;
        }
        if(vis[a][t.y]==0){//一大段的模拟
            vis[a][t.y]=1;
            q.push({a,t.y,t.s+" 1"});
        }
        if(vis[t.x][b]==0){
            vis[t.x][b]=1;
            q.push({t.x,b,t.s+" 2"});
        }
        if(vis[0][t.y]==0){
            vis[0][t.y]=1;
            q.push({0,t.y,t.s+" 3"});
        }
        if(vis[t.x][0]==0){
            vis[t.x][0]=1;
            q.push({t.x,0,t.s+" 4"});
        }
        while(t.x<a&&t.y>0){//A被倒满，或B被倒空
            t.x++;
            t.y--;
        }
        if(vis[t.x][t.y]==0){
            vis[t.x][t.y]=1;
            q.push({t.x,t.y,t.s+" 5"});
        }
        while(t.x>0&&t.y<b){//B被倒满，或A被倒空
            t.x--;
            t.y++;
        }
        if(vis[t.x][t.y]==0){
            vis[t.x][t.y]=1;
            q.push({t.x,t.y,t.s+" 6"});
        }
    }
    cout<<-1<<endl;
    return;
}
void init(){//初始化
    while(q.size()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    return;
}
void work(){
    init();
    cin>>a>>b>>n;
    bfs();
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}

5.\ 字串变换

这道题数据量非常小，爆搜就可以了。

广搜时对于每一次扩展，就看哪一条规则能匹配上，能匹配上就修改并入队列。

这里有个小小的坑，在匹配的时候，我们最好不要用 s.find() 因为 s.find() 找的是第一个匹配得上的，而一个字符串中可能不止一个匹配的上。

代码

#include<iostream>
#include<queue>
#include<cstring> 
#include<map>
using namespace std;
struct node{
    string s;
    int step;
};
queue<node>q;
map<string,bool>vis;
string a[10],b[10];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string A,B;
    cin>>A>>B;
    A+=" ";
    B+=" ";
    int cnt=1;
    while(cin>>a[cnt]>>b[cnt]){
        cnt++;
    }
    cnt--;
    if(A==B){
        cout<<0;
        return 0;
    } 
    q.push({A,0});
    vis[A]=1;
    while(q.size()){
        node t=q.front();
        q.pop();
        if(t.step>=10){
            continue;
        }
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<int(t.s.size())-int(a[i].size())+1;j++){
                if(t.s.substr(j,int(a[i].size()))==a[i]){
                    string tx=t.s.substr(0,j);
                    tx+=b[i];
                    tx+=t.s.substr(j+int(a[i].size()),int(t.s.size())-j-int(a[i].size()));
                    if(vis[tx]==1){
                        continue;
                    }
                    q.push({tx,t.step+1});
                    vis[tx]=1; 
                    if(tx==B){
                        cout<<t.step+1;
                        return 0;
                    }
                }
            }
        }
    }
    cout<<"NO ANSWER!";
    return 0;
}

6.\ 奇怪的电梯

这道题只用搜每一次是往上走，还是往下走即可，注意特判起点等于终点的情况。

代码

#include<iostream>
#include<queue>
#define int long long
using namespace std;
int a[205];
struct node{
    int x;
    int step;
};
queue<node>q;
int dx[3];
bool vis[205];
signed main(){
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(l==r){
        cout<<0;
        return 0;
    }
    q.push({l,0});
    vis[l]=1;
    while(q.size()){
        node t=q.front();
        q.pop();
        dx[0]=a[t.x];
        dx[1]=-dx[0];
        for(int i=0;i<2;i++){
            int tx=t.x+dx[i];
            if(tx<1||tx>n||vis[tx]==1){
                continue;
            }
            q.push({tx,t.step+1});
            vis[tx]=1;
            if(tx==r){
                cout<<t.step+1;
                return 0;
            }
        }
    }
    cout<<"-1";
    return 0;
}