搜索（dfs+bfs+回溯+记忆化搜索）

· · 个人记录

序言

搜索是什么？

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数，有一定的方向性和目标性。

搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。

搜索是一些高级算法的基础。在 OI 中，纯粹的搜索往往也是得到部分分的手段，但可以通过纯粹的搜索拿到满分的题目非常少。 (来自oiwiki)

目录QAQ

-序言

-目录

-1.dfs

-2.bfs

-3.回溯

-4.记忆化搜索

-5.好题分享

函数是一个非常简单的东西。

由于我在此篇博客里的所有搜索都是用函数写的，所以如果你不会函数的话请点这里QAQ点我,五分钟就可以懂了。如果不想看的话也没事，只是会造成一些理解上的问题。

另外，队列也是一个非常简单的东西。

由于bfs的实现是需要用队列来写的，所以如果你不会队列的话,可以来看看这里，也是一个非常简单的东西，五分钟以后也能回来。不看也会造成一些理解的问题，无伤大雅。

1.dfs

- dfs是什么？

- 如何实现？

//伪代码
dfs（v）{
    if 符合要求{
        操作
        返回
    }v上打标记 
    进行操作
    for u in v的相邻节点{
        if u没标记{
           dfs(u);
        }
    }
}

2.bfs

- bfs是什么？

最基础、最重要的搜索算法之一。 所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。 这样做的结果是，$bfs$算法找到的路径是从起点开始的 最短合法路径。换言之，这条路所包含的边数最小。 在$bfs$结束时，每个节点都是通过从起点到该点的最短路径访问的。(来自$oiwiki$)

- 实现？

//伪代码
bfs(初始节点 s){
    新队列 q
    s进队
    标记s
    while（队列不为空）{
        u=队首
        弹出
        for u的相邻结点v{
            if v未标记{
               操作
               v进队
            }
        }
    }
}

3.回溯

- 回溯是什么？

回溯法是一种经常被用在 深度优先搜索（dfs） 和 广度优先搜索（bfs） 的技巧。

其本质是：走不通就回头。 (来自oiwiki)

- 代码实现？

在本次放代码前先让我们考虑一道经典例题：全排列 P1706

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

对于这道题，我们考虑用一个布尔数组记录没用过的数字，再用一个ans数组记录选的是什么，具体实现请看代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans[110];
bool a[110];
void dfs(int s){
    if(s==n+1){
        for(int i=1;i<=n;i++){
            printf("    %d",ans[i]);
        }printf("\n");
        return;
    }for(int i=1;i<=n;i++){
        if(!a[i]){
            a[i]=true;
            ans[s]=i;
            dfs(s+1);
            a[i]=false;
        }
    }
}int main(){
    cin>>n;
    dfs(1);
    return 0;
}

那么接下来就奉上伪代码了QWQ

//伪代码
dfs（v）{
    if 符合要求{
        操作
        返回
    }进行操作
    for u in v的相邻节点{
        if u没标记{
           进行操作
           dfs(u);
           撤销操作
        }
    }
}

4.记忆化（讲完这个就正餐了QAQ）

- 记忆化搜索是什么？

最常用的剪枝有三种，记忆化搜索、最优性剪枝、可行性剪枝。

因为在搜索中，相同的传入值往往会带来相同的解，并且不比之前优的传入值还可能带来不比之前优的解，那我们就可以用数组来记忆。(oiwiki yyds!)

- 如何实现？

//伪代码
g[MAXN](记忆化数组)，ans=inf；
dfs(now(目前到的点),sum（总和）){
    if sum>g[now] return(之前走过的都比你这大了你还有机会麻QAQ);
    else{
        if(now==目的地){
            ans取最优;
            return;
        }else{
            for 遍历可能性{
                if 彳亍qwq!{
                    操作
                    dfs；
                    撤回操作
                }
            }
        }
    }
}......
int main(){
    ......
    初始化g极小/极大值；
    ......
}

5.好题分享

温馨提示：难度可能并不按顺序排序。

- 1 历年真题-棋盘

题面大意：给定你m*m的棋盘，每个棋盘都被染上了红色，黄色或者没被染色。如果你走向一个颜色相同的各自的话花费为0，走向不同颜色的格子的花费为1，让一个无色格子变为你想要的颜色（两轮）的花费为2，且不能连续使用。现在求从（1，1）走到（m,m）的最小花费。

对于100%的数据, 1≤m≤100,1≤n≤1000

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

对于这道题用搜索我们有两种方法——dfs与bfs

1.dfs做法：

对于dfs函数，我们考虑在它定义的参数中搞搞事情。

我的dfs一共定义了四个实参：nowx，nowy，spend，magic。其中nowx与nowy是表示现在到哪里了，而spend则代表目前花费，magic代表这一不可不可以使用魔法。再加上一个记忆化搜索，轻轻松松过了qwq。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int q[110][110],n,m,ans=1e9,d[110][110];
bool b[110][110];
int fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int nowx,int nowy,int spend,bool magic){
    if(nowx==m&&nowy==m){
        ans=min(ans,spend);
        return;
    }else{
        if(nowx>m||nowy>m||nowx<1||nowy<1){
            return;
        }else{
            for(int i=0;i<4;i++){
                int x=nowx+fx[i][0];int y=nowy+fx[i][1];
                if(b[x][y]) continue;
                if(q[x][y]!=0){
                    int nextspend=spend;
                    bool xk=true;
                    if(q[x][y]!=q[nowx][nowy]) nextspend++;
                    if(nextspend>=d[x][y]||nextspend>=ans) continue;
                    d[x][y]=nextspend;
                    b[x][y]=true;
                    dfs(x,y,nextspend,xk);
                    b[x][y]=false;
                }else{
                    if(magic){
                        bool xk=false;
                        int nextspend=spend+2;
                        if(nextspend>=d[x][y]||nextspend>=ans) continue;
                        d[x][y]=nextspend;
                        b[x][y]=true;
                        q[x][y]=q[nowx][nowy];
                        dfs(x,y,nextspend,xk);
                        b[x][y]=false;
                        q[x][y]=0;
                    }
                }
            }
        }
    }
}
int main(){
    cin>>m>>n;
    b[1][1]=true;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            d[i][j]=1e9;
        }
    }for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        q[x][y]=z+1;
    }dfs(1,1,0,1);
    if(ans==1e9) ans=-1;
    cout<<ans;
    return 0;
}

2.bfs做法

考虑优先队列+记忆化。

#include<bits/stdc++.h>
using namespace std;
int n,m,d[110][110],f[110][110];
int fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool b[110][110];
struct p{
    int nowx,nowy,spend,color;
    bool magic;
};struct cmp{
    bool operator()(p a,p b){
        return a.spend>b.spend;
    }
};
int bfs(int nx,int ny,int sp,bool ma){
    priority_queue<p,vector<p>,cmp> q;
    q.push({nx,ny,sp,d[nx][ny],ma});
    b[nx][ny]=true;
    while(!q.empty()){
        p s=q.top();
        q.pop();
        if(s.nowx>m||s.nowy>m||s.nowx<1||s.nowy<1||f[s.nowx][s.nowy]<s.spend) continue;
        f[s.nowx][s.nowy]=s.spend;
        b[s.nowx][s.nowy]=true;
        if(s.nowx==m&&s.nowy==m){
            return s.spend;
        }for(int i=0;i<=3;i++){
            int nextx=s.nowx+fx[i][0],nexty=s.nowy+fx[i][1];
            if(b[nextx][nexty]) continue;
            if(s.color==d[nextx][nexty]){
                q.push({nextx,nexty,s.spend,s.color,1});
            }else{
                if(d[nextx][nexty]==0){
                    if(s.magic){
                        q.push({nextx,nexty,s.spend+2,s.color,0});
                    }
                }else{
                    q.push({nextx,nexty,s.spend+1,d[nextx][nexty],1});
                }
            }
        }
    }return -1;
}int main(){
    memset(f,0x3f,sizeof(f));
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        d[x][y]=c+1;
    }int ans=bfs(1,1,0,1);
    cout<<ans;
    return 0;
}

- 2 练习好题-方格填数

题目大意：给你n以及n*n个数字，让你把这些数字让填入矩阵，使得每行每列每个对角线上整数的和都相等，并输出矩阵。如有多种填法，请输出字典序最小的。

其中3<=n<=4,-1e8<=a_i<=1e8

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

这道题只是一道绿题，难度也比较适中。

对于正解，我们可知其每行每列的sum便是所有的n*n个数字加起来再除以n.我们考虑dfs去枚举每个格子填什么数，定义nowi,nowj为目前枚举到的是ans[nowi][nowj]即可，对于每次即将枚举下一行的时候，进行剪枝即可（即每行加起来等不等于 加和/n ）。

对于最后，考虑暴力判断每行每列加起来等不等于 加和/n。

对于如何实现字典序，对输入进来的数进行排序即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[20],sum,ans[20][20];
bool b[20];
bool cmp(int a,int b){
    return a<b;
}void dfs(int nowi,int nowj){
    if(nowi==n+1){
        for(int j=1;j<=n;j++){
            int sum2=0;
            for(int i=1;i<=n;i++){
                sum2+=ans[i][j];
            }if(sum2!=sum) return;
        }int sum3=0,sum4=0;
        for(int i=1;i<=n;i++){
            sum3+=ans[i][i];
            sum4+=ans[i][n-i+1];
        }if(sum3!=sum||sum4!=sum){
            return;
        }else{
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    cout<<ans[i][j]<<" ";
                }cout<<"\n";
            }exit(0);
        }
    }else{
        if(nowj==n+1){
            int sum1=0;
            for(int j=1;j<=n;j++){
                sum1+=ans[nowi][j];
            }if(sum1==sum){
                dfs(nowi+1,1);
            }
        }else{
            for(int i=1;i<=n*n;i++){
                if(!b[i]){
                    b[i]=true;
                    ans[nowi][nowj]=a[i];
                    dfs(nowi,nowj+1);
                    b[i]=false;
                }
            }
        }
    }
}signed main(){
    cin>>n;
    for(int i=1;i<=n*n;i++){
        cin>>a[i];
        sum+=a[i];
    }sum/=n;
    sort(a+1,a+(n*n)+1,cmp);
    cout<<sum<<"\n";
    dfs(1,1);
    return 0;
}

- 3 历年真题-矩形覆盖

题目大意：给你n个点的坐标x，y，让你用不互相重复的k个矩形去覆盖他们，问这k个矩形的最小总面积。

其中n<=50,k<=4,0<x，y<=500

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

对于正确做法，我们考虑dfs暴搜——考虑哪个点归类到哪一个矩形里,每一次更新完矩形的最小面积就判断这些矩形有没有重叠部分。那么这样时间复杂度是O(nk^2xy)的，不会超时。

#include<bits/stdc++.h>
using namespace std;
// P1034
int n,k,ans=1e9,nx[100],ny[100];
struct M{
    int x[10],y[10];
    bool yes;
} t[10];
void dfs(int step,int s){
    if(s>=ans) return;
    else{
        if(step==n+1){
            for(int i=1;i<=k;i++){
                for(int j=1;j<=k;j++){
                    if(i==j){
                        continue;
                    }else{
                        for(int nowx=t[j].x[1];nowx>=t[j].x[2];nowx--){
                            for(int nowy=t[j].y[2];nowy>=t[j].y[1];nowy--){
                                if(t[i].x[1]>=nowx&&t[i].x[2]<=nowx&&t[i].y[2]>=nowy&&t[i].y[1]<=nowy){
                                    return;
                                }
                            }
                        }
                    }
                }
            }int sum=0;
            for(int i=1;i<=k;i++){
                sum+=(t[i].x[1]-t[i].x[2])*(t[i].y[2]-t[i].y[1]);
            }ans=min(sum,ans);
            return;
        }else{
            for(int i=1;i<=k;i++){
                M lzm=t[i];
                if(!t[i].yes){
                    t[i].x[1]=t[i].x[2]=ny[step];
                    t[i].y[1]=t[i].y[2]=nx[step];
                    t[i].yes=true;
                }else{
                    if(nx[step]<t[i].y[1]){
                        t[i].y[1]=nx[step];
                    }else{
                        if(nx[step]>t[i].y[2]){
                            t[i].y[2]=nx[step];
                        }
                    }if(ny[step]>t[i].x[1]){
                        t[i].x[1]=ny[step];
                    }else{
                        if(ny[step]<t[i].x[2]){
                            t[i].x[2]=ny[step];
                        }
                    }
                }int sum=0;
                for(int i=1;i<=k;i++){
                    sum+=(t[i].x[1]-t[i].x[2])*(t[i].y[2]-t[i].y[1]);
                }dfs(step+1,sum);
                t[i]=lzm;
            }
        }
    }
}int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>nx[i]>>ny[i];
    }dfs(1,0);
    cout<<ans;
}

-4 历年真题-虫食算

题意简述：给你n以及三行长度为n的字符串，上两行代表加数，最后一行代表结果。现在告诉你相同的字母代表相同的数字并且这个算式是n进制的，求最后A,B......（我们规定用前n个字母来代表0-n）所代表的数字。

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

先来夹带一点私货。

改了一个月

对于这道题而言我们首先考虑到的是产生n个数的全排列，再去一个个检查，但是很显然，对于极限数据来讲它的时间复杂度肯定会爆炸。

接下来我们去考虑剪枝。

首先第一个剪枝，便是我们边搜边去检查，又没有不合法的地方。在没有确定进位的情况下，只要不符合(A+B+(0/1)) mod n=C的就可以剪掉了。

接下来第二个剪枝，便是我们考虑从最低位搜起，这样的话能使第一个剪枝跑的飞快。

其实接下来还有一个玄学的优化：便是从n-1搜到0,其实我也不知道为什么这样跑能更快，可能是因为首位不能进位的原因。。。

#include<bits/stdc++.h>
using namespace std;
int a[30],b[30],c[30],nex[30],nextop,num[30],n;
char sta[30],stb[30],stc[30];
bool nu[30];
bool CP(){
    for(int i=1;i<=n;i++){
        if(num[a[i]]==-1||num[b[i]]==-1||num[c[i]]==-1){
            continue;
        }else{
            int t=num[a[i]]+num[b[i]];
            if(!(((t+1)%n!=num[c[i]])^((t)%n!=num[c[i]]))){
                return 1;
            }
        }
    }return 0;
}bool J(){
    for(int i=1,x=0;i<=n;i++){
        int t=(num[a[i]]+num[b[i]]+x);
        if(t%n!=num[c[i]]){
            return 1;
        }x=t/n;
    }return 0;
}void init(){
    for(int i=1;i<=n;i++){
        a[i]=(sta[n-i]-'A')+1;
        b[i]=(stb[n-i]-'A')+1;
        c[i]=(stc[n-i]-'A')+1;
    }return;
}void print(){
    for(int i=1;i<n;i++){
        cout<<num[i]<<" ";
    }cout<<num[n]<<"\n";
    exit(0);
}void dfs(int step){
    if(CP()) return;
    if(step==n+1){
        if(J()) return;
        else{
            print();
            return;
        }
    }else{
        for(int i=n-1;i>=0;i--){
            if(!nu[i]){
                nu[i]=1;
                num[nex[step]]=i;
                dfs(step+1);
                num[nex[step]]=-1;
                nu[i]=0;
            }
        }
    }
}void GN(int x){
    if(!nu[x]){
        nu[x]=1;
        nextop++;
        nex[nextop]=x;
    }return;
}int main(){
    //cout<<1<<" ";
    scanf("%d",&n);
    scanf("%s",sta);
    scanf("%s",stb);
    scanf("%s",stc);
    //cout<<sta<<'\n'<<stb<<'\n'<<stc<<'\n';
    for(int i=n-1;i>=0;i--){
        num[i]=-1;
    }init();
    for(int i=1;i<=n;i++){
        GN(a[i]);
        GN(b[i]);
        GN(c[i]);
    }memset(nu,0,sizeof(nu));
    dfs(1);
    return 0;
}

-5 练习好题-幻象迷宫

题目大意：给你一个行为n,列为m的由字符 # , . ,S组成的矩阵迷宫。其中#代表障碍，.代表可走的路，S代表起点。

我们认为这个矩阵迷宫是可以无限延伸的。而我们在规定走出去的定义是能够走出无限远的距离。现在请你判断给你的迷宫可不可以走出去。

输入有多组数据，其中n,m \le 1500。

输入文件以EOF结尾

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

（防剧透QAQ）

这道题其实用bfs,dfs都可做，但是因为理解了bfs做法dfs就基本上可以写了。(绝对不是因为我懒) 所以只讨论bfs做法。

首先，将迷宫拓展这种做法是不可取的。首先，这一组数据就能够卡掉你:

6 20
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
S.#..#..#..#..#..#..
##..#..#..#..#..#..#
#..#..#..#..#..#..##

那怎么办呢？

我们注意到，因为它是可以无限拓展的，所以你在(x,y)上其实就相当于在原矩阵的(( x\bmod{n}+n)\bmod{n},( y\bmod{m}+m)\bmod{m})上。所以我们考虑去记录每个真实坐标的lx,ly与取模后的坐标x,y。

那么，对于每一个原矩阵的格子，我们考虑去记录上一个取模后坐标与它相等的真实坐标。如果上一次与这一次的真实坐标不相等，那么直接返回，因为它可以走无限远后又回到这个点。而相等的话就可以直接找下一个了，因为你其实就相当于在这几个格子之间反复横跳。

上代码：

#include<iostream>
#include<queue>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ni,nj,x[4]={0,1,0,-1},y[4]={1,0,-1,0},vis[1510][1510][2],finf;
bool Map[1510][1510];
struct node{
    int i,j,li,lj;
};bool bfs(){
    queue<node> q;
    node s={ni,nj,ni,nj};
    q.push(s);
    while(!q.empty()){
        node s=q.front();
        q.pop();
        if(vis[s.i][s.j][0]==s.li&&vis[s.i][s.j][1]==s.lj){
            continue;
        }else{
            if((vis[s.i][s.j][0]!=s.li||vis[s.i][s.j][1]!=s.lj)&&(vis[s.i][s.j][0]!=finf&&vis[s.i][s.j][1]!=finf)){
                return true;
            }
        }vis[s.i][s.j][0]=s.li;
        vis[s.i][s.j][1]=s.lj;
        for(int i=0;i<=3;i++){
            int mi=(s.i+x[i]+n)%n,mj=(s.j+y[i]+m)%m,nmi=(s.li+x[i]),nmj=(s.lj+y[i]);
            if(Map[mi][mj]){
                q.push({mi,mj,nmi,nmj});
            }
        }
    }return false;
}signed main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(vis,-1,sizeof(vis));
        finf=vis[1][1][1];
        for(int i=0;i<n;i++){
            char s[1510];
            scanf("%s",s);
            for(int j=0;j<m;j++){
                if(s[j]=='.'||s[j]=='S'){
                    Map[i][j]=true;
                    if(s[j]=='S'){
                        ni=i;nj=j;
                    }
                }else{
                    Map[i][j]=false;
                }
            }
        }bool maybe=bfs();
        if(maybe){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    return 0;
}

完结撒花(*^-^*)