搜索

程序员文章站 2022-03-25 17:26:03

搜索 [TOC] 前言搞了半个月的搜索，写的头都要炸了，不过貌似还是有提升的。终于把书上的基础搜索算法康完了，于是有了这篇文章。其实就是在本书基础上加上自己的理解~~（作为OIer，感觉看电脑就是比看书舒服）~~，以下是正文部分。一、树与图的遍历其实和搜索的关系不大，但基于搜索实现，而且还 ......

搜索

前言

搞了半个月的搜索，写的头都要炸了，不过貌似还是有提升的。

终于把书上的基础搜索算法康完了，于是有了这篇文章。

其实就是在本书基础上加上自己的理解~~（作为oier，感觉看电脑就是比看书舒服）~~，以下是正文部分。

一、树与图的遍历

其实和搜索的关系不大，但基于搜索实现，而且还蛮有用的。

树与图的dfs遍历、树的dfs序、深度和重心

遍历

这个...很基础了，直接上代码吧：

void dfs(int x){
    v[x]=1;
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
    }
}

复杂度 $o(n+m)$ 。

按上述方法遍历每一个节点的顺序被称为树的 $dfs$ 序。

而按上述顺序按第一次被遍历的时间给每一个节点 1~n 的标记，这个标记被称为时间戳。

树的深度

已知根节点的深度为 0 ，若节点 $x$ 的深度为 $d[x]$ ，其子节点 $y$ 的深度为 $d[y]=d[x]+1$ 。

代码见下：

void dfs(int x){
    v[x]=1;
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(v[y]) continue;
        d[y]=d[x]+1;
        dfs(y);
    }
}

~~其实就多了一句话~~

树的重心

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心。

至于怎么找重心，其实一遍 $dfs$ 就可以了。

当遍历到一个节点时，它的子节点的大小在回溯时可以直接统计，

关键是怎么求以它为根，向上发展的一颗子树，然后你会发现那就是 $n-size[x]$ （其中 $n$ 为总结点数）

代码如下：

void dfs(int x){
    v[x]=1;size[x]=1;
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
        size[x]+=size[y];
        max_part=max(max_part,size[y]);
    }
    max_part=max(max_part,n-size[x]);
    if(max_part<ans){
        ans=max_part;
        pos=x;
    }
}

图的连通块的划分

很简单的，直接上代码：

void dfs(int x){
    v[x]=cnt;
    for(int i=head[x];i;i=next[i]){
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
    }
}
int main(){
    for(int i=1;i<=n;i++)
        if(!v[i]){
            cnt++;
            dfs(i);
        }
}

树与图的bfs遍历、拓扑排序

遍历

很简单~~（请不要认为一下都很简单，只要你不是神犇，越往下看你会越自闭）~~

void bfs(){
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(1);d[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=next[i]){
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            q.push(y);
        }
    }
}

bfs是一种按照层次顺序遍历的算法，它具有以下两个重要性质：

在访问完第 $i$ 层节点后再访问 $i+1$ 层。（两段性）
任何时刻，队列中至多有两层节点（$i$ 和 $i+1$ 层），而且第 $i$ 层的节点一定在第 $i+1$ 层之前。（单调性）

和 dfs 一样，时间为 $o(n+m)$ 。

拓扑排序

在图论中，拓扑排序（topological sorting）是一个有向无环图（dag, directed acyclic graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。
若存在一条从顶点 a 到顶点 b 的路径，那么在序列中顶点 a 出现在顶点 b 的前面。

有向无环图（dag）才有拓扑排序，非dag图没有拓扑排序一说。

找到图中入度为0的点（即没有边以它为终点的点），把它放入队列。
取出队列中的点，输出之，删掉与之相邻的边，并把那些边的终点的入度减1。
重复1，2步，直至本图为空或图中没有入度为0的点时，结束。（后一种情况表明图中有环）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#define maxn 10010
#define maxm 100010
using namespace std;

int n,m,fa[maxn],sum=0;
int head[maxm],cnt=0;
struct node{
    int to,next;
}edge[maxm];

queue<int>q;

void addedge(int x,int y){
    cnt++;
    edge[cnt].next=head[x];
    edge[cnt].to=y;
    head[x]=cnt;
}

void topo(){
    for(int i=1;i<=n;i++){
        if(!fa[i]) q.push(i);//预处理入度为0的点入队 
    }
    
    while(!q.empty()){
        int now=q.front();
        q.pop();
        sum++;
        printf("%d\n",now);
        for(int i=head[now];i;i=edge[i].next){
            if(!--fa[edge[i].to]) q.push(edge[i].to);
        }
    } 
    if(sum<n) printf("false\n");
    return;
}

int main(){
    scanf("%d %d",&n,&m);
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d %d",&a,&b);
        fa[b]++;
        addedge(a,b);
    }
    topo();
    return 0;
}

例题

可达性问题

具体见书p95。

给定一个n个点，m条边的有向无环图，问每个点直接或间接可到达的点的数量。

书中有详细介绍，这里就不再赘述了，简而言之就是 拓扑排序+状态压缩 。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<bitset>
#include<vector>
#include<queue>
#define n 30030
#define m 30030
using namespace std;

int n,m,f[n],side[n];
int head[n],cnt=0;
struct node{
    int to,next;
}edge[m];

vector<int>path;
bitset<m>b[n];
queue<int>q;

void addedge(int x,int y){
    cnt++;
    edge[cnt].next=head[x];
    edge[cnt].to=y;
    head[x]=cnt;
    return;
}

void topo(){
    for(int i=1;i<=n;i++){
        if(!side[i]) q.push(i);
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        path.push_back(now);
        for(int i=head[now];i;i=edge[i].next){
            int y=edge[i].to;
            if(!--side[y]) q.push(y);
        }
    }
    return;
}

int main(){
    memset(side,0,sizeof(side));
    scanf("%d %d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        addedge(u,v);
        side[v]++;
    }
    topo();
    for(int i=path.size()-1;i>=0;i--){
        int u=path[i];
        b[u][u]=1;
        for(int j=head[u];j;j=edge[j].next){
            int v=edge[j].to;
            b[u]|=b[v];
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",b[i].count());
    }
    return 0;
}

二、深度优先搜索及剪枝

dfs简述

其搜索方式为，在某个状态a，找到一个可以由此状态转移到的状态b，然后转移到状态b，遍历完b所有的后续状态后，返回状态a，再寻找a的另一个可转移状态c，如此往复，直至所有状态被遍历完。
更通俗地说，即在遍历时，优先选择一条路，往搜索树的深层遍历，当不能继续深入时则返回上一层，选择另一个岔路遍历。

代码框架大概是这个样子：

void dfs(...){//搜索状态
    if(...) return;//终止条件及剪枝
    for(...){//遍历子节点
        ...//进入下一层之前的处理
        dfs(...)//进入下一层
        ...//回溯
    }
    return;//结束
}

因为基本知识就这么多，主要依靠例题来讲解。

dfs例题

小猫爬山

ch2201 小猫爬山

主要思路书上讲的很详细了，这里提一下两个剪枝：

最优化剪枝：一旦目前的 $cnt>ans$ ，果断 $return$ 。
优化搜索顺序：重的猫一定比轻的猫要占空间，所以按照重量递减排序。

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define n 25
#define maxd 999999999
using namespace std;

int n,c[n],m;
int cab[n],ans=maxd;

void dfs(int now,int cnt){
    if(now>n){
        ans=min(ans,cnt);
        return;
    }
    if(cnt>=ans) return;//剪枝1

    for(int i=1;i<=cnt;i++){
        if(c[now]+cab[i]<=m){
            cab[i]+=c[now];
            dfs(now+1,cnt);
            cab[i]-=c[now];
        }
    }
    cab[cnt+1]=c[now];
    dfs(now+1,cnt+1);
    cab[cnt+1]=0;
    return;
}

bool cmp(int a,int b){
    return a>b;
}

int main(){
     scanf("%d %d",&n,&m);
     for(int i=1;i<=n;i++) scanf("%d",&c[i]);
     sort(c+1,c+n+1,cmp);//剪枝2
     dfs(1,0);
     printf("%d\n",ans);
     //system("pasue");
     return 0;
}

sudoku

poj2676 sudoku

具体思路同样被讲的很详细了，这里同样不再赘述。（书上讲的很多优化我没有用到，但还是能过的）

代码见下：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

int a[20][20];
bool h[20][20],l[20][20],g[20][20];
bool flag;

int find(int x,int y){
    return (x-1)/3*3+(y-1)/3+1;
}

void print(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            printf("%d",a[i][j]);
        }
        printf("\n");
    }
    flag=true;
}

void dfs(int x,int y){
    if(flag) return;
    if(a[x][y]){
        if(x==9 && y==9) print();
        if(y==9) dfs(x+1,1);
        else dfs(x,y+1);
    }
    else{
        for(int i=1;i<=9;i++){
            if(h[x][i]&&l[y][i]&&g[find(x,y)][i]){
                a[x][y]=i;
                h[x][i]=l[y][i]=g[find(x,y)][i]=false;
                if(x==9&&y==9) print();
                if(y==9) dfs(x+1,1); else dfs(x,y+1);
                a[x][y]=0;
                h[x][i]=l[y][i]=g[find(x,y)][i]=true;
            }
        }
    }
    return;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        flag=false;
        memset(h,true,sizeof(h));
        memset(l,true,sizeof(l));
        memset(g,true,sizeof(g));
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                scanf("%1d",&a[i][j]);
                if(a[i][j]==0) continue;
                h[i][a[i][j]]=false;
                l[j][a[i][j]]=false;
                g[find(i,j)][a[i][j]]=false;
            }
        }
        dfs(1,1);
    }
    return 0;
}

剪枝

搜索的灵魂，暴力的核心~~（只要剪枝写得好，直接暴力踩标算）~~

剪枝：缩小搜索规模以达到时间上的优化，因类似于剪掉搜索树的枝条，所以形象地称为剪枝。

常见的剪枝方法如下：

优化搜索顺序：由于每种搜索顺序所形成的搜索树形态各异，规模大小也相去甚远，例如：
- 小猫爬山问题：按照重量递减排序。
排除等效冗余：如果能确定两颗搜索树是等效的，显然只需要搜索其中一颗。
可行性剪枝：如果发现前方是“死胡同”，就直接回头。例如某些题目的范围限制是一个区间。
最优化剪枝：如果当前花费的代价已经 $>ans$ ，无论后面再怎么优秀，都不可能刷新答案。
记忆化：如果一颗子树的值需要重复利用多次，最好的方法是直接把这个值给记录下来。
- 如果你丧心病狂地拿 dfs 写斐波那契数列，你一定深有体会。

接下来让我们用几道例题来感受剪枝的妙用。

剪枝例题

sticks

p1120 小木棍

具体剪枝思路看书。

代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

int n,cnt,len,a[70];
bool use[70];

bool dfs(int stick,int cab,int last){
    if(stick>cnt) return true;
    if(cab==len) return dfs(stick+1,0,1);
    int fail=0;
    for(int i=last;i<=n;i++){//剪枝1
        if(!use[i] && cab+a[i]<=len && a[i]!=fail){
            use[i]=true;
            if(dfs(stick,cab+a[i],i+1)) return true;
            fail=a[i];//剪枝2
            use[i]=false;
            if(cab+a[i]==len || cab==0) return false;//剪枝3、4
        }
    }
    return false;
}

bool cmp(int a,int b){
    return a>b;
}

int main(){
    int o,val=0,sum=0;
    scanf("%d",&o);
    for(int i=1;i<=o;i++){
        int p;
        scanf("%d",&p);
        if(p<=50){
            a[++n]=p;
            sum+=p;
            val=max(val,p);
        }
    }
    sort(a+1,a+n+1,cmp);//优化搜索顺序
    for(len=val;len<=sum;len++){
        if(sum%len) continue;
        memset(use,false,sizeof(use));
        cnt=sum/len;
        if(dfs(1,0,1)) break;
    }
    printf("%d\n",len);
    return 0;
}

生日蛋糕

p1731 生日蛋糕

搜索鼻祖，gy说：“你会了生日蛋糕，你就会了剪枝。”

说了很多次的话不想重复。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define maxn 2147483647
using namespace std;

int n,m,mins[20],minv[20],ans=maxn;

void dfs(int s,int v,int step,int r,int h){
    if(step==0){
        if(v==n) ans=min(ans,s);
        return;
    }
    //possible剪枝
    if(s+mins[step-1]>ans) return;
    if(v+minv[step-1]>n) return;
    //best剪枝
    if(s+2*(n-v)/r>=ans) return;
    //next
    for(int i=r-1;i>=step;i--){
        if(m==step) s=i*i;
        int maxh=min(h-1,(n-v-minv[step-1])/(i*i));
        for(int j=maxh;j>=step;j--){
            dfs(s+2*i*j,v+i*i*j,step-1,i,j);
        }
    }
    return;
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        mins[i]=mins[i-1]+2*i*i;//预处理最小面积
        minv[i]=minv[i-1]+i*i*i;//预处理最小体积
    }
    
    dfs(0,0,m,n+1,n+1);
    
    if(ans==maxn){
        printf("0\n");
        return 0;
    }
    printf("%d\n",ans);
    return 0;
}

三、迭代加深及dfs常见优化

迭代加深

dfs有一个缺陷，就是每次必须选定一个分支，直到终点才回溯。

假设每个节点的分支非常多，答案在很浅的节点上，而一开始就选错了分支，你就gg了。

所以就有了迭代加深（id）算法，具体流程如下：

迭代加深以dfs为基础，本质上仍然是dfs。
从1开始，从小到大枚举一个深度界限d。
枚举d的同时进行dfs，并规定此次dfs的深度不能超过d。
当dfs搜索到目标时停止，此时的d值就是能够搜索到答案的最小深度。

你可能会很奇怪，每一次迭代不都重复计算了很多节点吗？这不会t吗？

答案是，即使重复搜索，每层的节点都是指数级增长，即使重复搜索 \[1\]~\[d-1\] ，其时间消耗可能还不及第 $d$ 层。

所以不用担心重复的问题。

总而言之：当搜索树规模随着层数的深入而增长很快，而且答案在一个较浅层的节点，就可以用id算法。

例题

岳麓山打水

岳麓山打水 vijos1159

好像是模板题，自己理解吧：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define maxn 20020
using namespace std;

int n,m,a[maxn],p[maxn],d;
bool f[maxn];

bool chck(){
    memset(f,false,sizeof(f));
    f[0]=true;
    for(int i=1;i<=d;i++){
        for(int j=0;j+p[i]<=m;j++){
            if(f[j]) f[j+p[i]]=true; 
        }
    }
    return f[m];
}

bool dfs(int x,int y){
    if(x>d) return (chck());
    for(int i=y;i<=n;i++){
        p[x]=a[i];
        if(dfs(x+1,i+1)) return true;
    }
    return false;
}

int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    
    for(d=1;;d++){
        if(dfs(1,1)) break;
    }
    printf("%d ",d);
    for(int i=1;i<=d;i++) printf("%d ",p[i]);
    return 0;
}

双向搜索

简单说就是从初态和终态出发各搜索一般状态，产生两棵深度减半的搜索树，在中间交汇，组成最终答案。

有效地避免了层数过深时的大规模增长，但前提是已知目标状态。

其实很好写，例题就不在赘述了。

四、广度优先搜索及其优化

广度优先搜索

在之前就已经讲述了图的bfs遍历，如果我们把搜索树看成一张图，在遍历时顺便做一些处理，这就变成了bfs。

很简单的介绍，主要通过例题来加强认识吧。

例题

bloxorz

bloxorz poj3322

这是一道经典的 走地图 类的问题，这类问题可以用bfs来解决（具体见书）

因为书上有标程，~~而且还写得挺好~~，这里皆采用书上方法实现：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#define maxn 550
using namespace std;

struct node{
    int x,y,lin;
}st,ed;
int n,m,f[maxn][maxn][5];//0直立，1横放（左为x,y），2竖放（上为x,y） 
char s[maxn][maxn];
int dx[5]={0,0,-1,1};//左右上下 
int dy[5]={-1,1,0,0};
int next_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
int next_y[3][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
int next_lin[3][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};
queue<node>q;

bool in(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}

void pre_work(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='o'){ed.x=i;ed.y=j;ed.lin=0;s[i][j]='.';}
            else if(s[i][j]=='x'){
                //bool flag=false;
                for(int k=0;k<=3;k++){
                    int x=i+dx[k];
                    int y=j+dy[k];
                    if(in(x,y)&&s[x][y]=='x'){
                        //flag=true;
                        st.x=min(i,x);st.y=min(j,y);
                        st.lin=k<2?1:2;
                        s[i][j]=s[x][y]='.';
                        break;
                    }
                }
                if(s[i][j]=='x'){st.x=i;st.y=j;st.lin=0;}
            }
    return;
}

bool able(node next){
    if(!in(next.x,next.y)) return false;
    if(s[next.x][next.y]=='#') return false;
    if(next.lin==0&&s[next.x][next.y]!='.') return false;
    if(next.lin==1&&s[next.x][next.y+1]=='#') return false;
    if(next.lin==2&&s[next.x+1][next.y]=='#') return false;
    return true;
}

int bfs(){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=2;k++)
            f[i][j][k]=-1;
        }
    }
    f[st.x][st.y][st.lin]=0;
    q.push(st);
    
    while(!q.empty()){
        node now=q.front();q.pop();
        for(int i=0;i<=3;i++){
            node next;
            next.x=now.x+next_x[now.lin][i];
            next.y=now.y+next_y[now.lin][i];
            next.lin=next_lin[now.lin][i];
            if(!able(next)) continue;
            if(f[next.x][next.y][next.lin]==-1){
                f[next.x][next.y][next.lin]=f[now.x][now.y][now.lin]+1;
                q.push(next);
                if(ed.x==next.x&&ed.y==next.y&&ed.lin==next.lin) return f[next.x][next.y][next.lin];
            }
        }
    }
    return -1;
}

int main(){
    while(~scanf("%d %d",&n,&m)&&n){
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        pre_work();
        //printf("%d %d %d\n%d %d %d\n",st.x,st.y,st.lin,ed.x,ed.y,ed.lin);
        int ans=bfs();
        if(ans==-1) printf("impossible\n");else printf("%d\n",ans);
    }
    return 0;
}

~~好像码量还挺大~~

pushing boxes

pushing boxes poj1475

同样是 走地图 式的题目，但是好恶心！（思路书上有）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<iostream>
#include<string>
#define maxn 25
using namespace std;

int n,m,px,py,bx,by;
char a[maxn][maxn];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
char box_path[5]="snew";
char man_path[5]="snew";
bool box_vis[maxn][maxn];
bool man_vis[maxn][maxn];
string pathman;
struct man{
    int x,y;
    string path;    
};
struct box{
    int x,y;
    int mx,my;
    string path;
};

bool in(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}

bool bfs_man(int cantx,int canty,int sx,int sy,int ex,int ey){
    memset(man_vis,0,sizeof(man_vis));
    man p;
    pathman="";
    if(ex<1||ex>n||ey<1||ey>m) return false;
    p.x=sx;p.y=sy;p.path="";
    man_vis[sx][sy]=true;
    queue<man>q;
    q.push(p);
    
    while(!q.empty()){
        man now=q.front();
        q.pop();
        if(now.x==ex&&now.y==ey){
            pathman=now.path;
            return true;
        }
        for(int i=0;i<=3;i++){
            int gx=now.x+dx[i];
            int gy=now.y+dy[i];
            if(gx==cantx && gy==canty) continue;
            if(in(gx,gy)&&!man_vis[gx][gy]&&a[gx][gy]!='#'){
                man_vis[gx][gy]=true;               
                p.x=gx;p.y=gy;
                p.path=now.path+man_path[i];
                q.push(p);
            }
        }
    }
    return false;
}

void bfs_box(){
    memset(box_vis,0,sizeof(box_vis));
    queue<box>q;
    box p;
    p.x=bx;
    p.y=by;
    p.mx=px;
    p.my=py;
    p.path="";
    box_vis[bx][by]=true;
    q.push(p);
    
    while(!q.empty()){
        box now=q.front();
        q.pop();
        for(int i=0;i<=3;i++){
            int gx=now.x+dx[i];
            int gy=now.y+dy[i];
            if(in(gx,gy)&&a[gx][gy]!='#'&&!box_vis[gx][gy]&&
            bfs_man(now.x,now.y,now.mx,now.my,now.x-dx[i],now.y-dy[i])){
                box_vis[gx][gy]=true;
                p.x=gx;p.y=gy;
                p.mx=now.x;p.my=now.y;
                p.path=now.path+pathman+box_path[i];
                if(a[gx][gy]=='t'){
                    cout << p.path << endl;
                    return;
                }
                q.push(p);
            }
        }
    }
    printf("impossible.\n");
    return;
}

int main(){
    int cnt=0;
    while(~scanf("%d %d",&n,&m)&&n){
        for(int i=1;i<=n;i++){
            scanf("%s",a[i]+1);
            for(int j=1;j<=m;j++){
                if(a[i][j]=='s'){
                    px=i;py=j;
                }
                else if(a[i][j]=='b'){
                    bx=i;by=j;
                }
            }
        }
        printf("maze #%d\n",++ cnt);
        bfs_box();
        printf("\n");
    }
    return 0;
}

双端队列bfs

在以上的bfs算法之中，每走一步的代价始终是 $1$ ，但如果不仅仅是 $1$ 我们还算得出来吗？

别急，先看边权是 $0$ 或 $1$ ，的情况。

电路维修 ch2601

其实很简单的啦，在一张边权要么是0，要么是1的无向图上，我们可以通过双端队列bfs来实现搜索。

大体和基础广搜类似，只是如果一味往队尾添加元素的话，无法满足单调性（1有可能在0的前面）

所以当边权是0时，插入队头，否则插入队位，然后就和正常广搜一样了。~~（不懂 $deque$ 请自行百度）~~

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<deque>
#define n 550
#define m 3000000
using namespace std;

int n,m,t,f[n*n];
char a[n][n];
int head[n*n],cnt=0;
struct node{
    int to,next,val;
}edge[m];
deque<int>q;

int get_num(int x,int y){
    return x*(m+1)+y+1;
}

void addedge(int x,int y,int z){
    cnt++;
    edge[cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].val=z;
    head[x]=cnt;
    return;
}

void bfs(){
    while(!q.empty()) q.pop_front();
    for(int i=0;i<=(n+1)*(m+1);i++) f[i]=-1;
    f[1]=0;
    q.push_front(1);
    
    while(!q.empty()){
        int now=q.front();
        q.pop_front();
        if(now==(n+1)*(m+1)){
            printf("%d\n",f[now]);
            return;
        }
        for(int i=head[now];i;i=edge[i].next){
            int y=edge[i].to;
            int z=edge[i].val;
            if(f[y]==-1||f[y]>f[now]+z){
                f[y]=f[now]+z;
                if(z) q.push_back(y);
                else q.push_front(y);
            }
        }
    }
    printf("no solution\n");
    return;
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        cnt=0;
        memset(head,0,sizeof(head));
        for(int i=1;i<=n;i++){
            scanf("%s",a[n]+1);
            for(int j=1;j<=m;j++){
                if(a[i][j]=='/'){
                    addedge(get_num(i-1,j-1),get_num(i,j),1);//气
                    addedge(get_num(i,j),get_num(i-1,j-1),1);//势
                    addedge(get_num(i-1,j),get_num(i,j-1),0);//磅
                    addedge(get_num(i,j-1),get_num(i-1,j),0);//礴
                }
                else{
                    addedge(get_num(i-1,j-1),get_num(i,j),0);//的
                    addedge(get_num(i,j),get_num(i-1,j-1),0);//存
                    addedge(get_num(i-1,j),get_num(i,j-1),1);//图
                    addedge(get_num(i,j-1),get_num(i-1,j),1);//啊（这个是凑字用的）
                }
            }
        }
        bfs();
    }
}

优先队列bfs

对于更具有普适性的算法，边权为任意值怎么做呢？

方法一：当有负权时

任然如一般广搜一般，采用队列。
不能保证每个状态第一次入队时就得到最小代价，所以允许多次重复遍历与更新。
具体请看最短路中的 $spfa$ 算法。
ps：复杂度为玄学。

方法二：当无负权时

采用优先队列bfs。
能够保证每个状态第一次入队时就得到最小代价，所以每个节点至多入队一次。
具体请看最短路中的 $dijkstral$ 算法。
ps：复杂度 $o(n log n)$ 。

~~that's so easy that i don't want to say any more.~~

双向广搜

其实没什么两样，就是两边轮流进行，每次扩展一层。

例题：nightmare ⅱ hdoj3085

很简单的双向广搜题，但要注意男孩走三层，女孩走一层。（就被这个坑了 $inf$ 次）

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define maxn 810
using namespace std;

int n,m,f[maxn][maxn];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
bool vis[maxn][maxn][2];
char s[maxn][maxn];
struct point{
    int x,y;
};
point mm,gg,go[2];
queue<point>q[2];

void init(){
    int t=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++){
            if(s[i][j]=='m'){mm.x=i;mm.y=j;}
            else if(s[i][j]=='g'){gg.x=i;gg.y=j;}
            else if(s[i][j]=='z'){go[t].x=i;go[t++].y=j;}
        }
    }
    return;
}

void pre_work(){
    while(!q[0].empty()) q[0].pop();
    while(!q[1].empty()) q[1].pop();
    memset(vis,false,sizeof(vis));
    return;
}

int dis(int x1,int y1,int x2,int y2){
    return abs(x1-x2)+abs(y1-y2);
}

bool chck(int x,int y,int typ,int step){
    if(x<1 || x>n || y<1 || y>m || s[x][y]=='x') return false; 
    for(int i=0;i<=1;i++){
        if(dis(x,y,go[i].x,go[i].y)<=step*2) return false;
    }
    return true;
}

bool bfs(int typ,int step){
    int si=q[typ].size();
    while(si--){
        point now=q[typ].front();
        q[typ].pop();
        if(!chck(now.x,now.y,typ,step)) continue;
        for(int i=1;i<=4;i++){
            int fx=now.x+dx[i];
            int fy=now.y+dy[i];
            if(!chck(fx,fy,typ,step)||vis[fx][fy][typ]) continue;
            if(vis[fx][fy][typ^1]) return true;
            vis[fx][fy][typ]=true;
            q[typ].push((point){fx,fy});
        }
    }
    return false;
}

void work(){
    pre_work();
    vis[mm.x][mm.y][0]=true;
    vis[gg.x][gg.y][1]=true;
    q[0].push((point){mm.x,mm.y});
    q[1].push((point){gg.x,gg.y});
    int step=0;
    while(!q[0].empty() || !q[1].empty()){
        step++;
        for(int i=1;i<=3;i++){
            if(bfs(0,step)){
                printf("%d\n",step);
                return;
            }
        }
        if(bfs(1,step)){
            printf("%d\n",step);
            return;
        }
    }
    printf("-1\n");
    return;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        work();
    }
    return 0;
}

五、a*算法

a*简述

难度真心很大，在优先队列bfs算法，如果给定目标状态要求求出到达目标状态的最小代价，显然它不够优。

因为它是建立在贪心的基础之上的，但目前最优不代表以后最优。

所以为了提高搜索效率，我们可以设置一个估价函数，计算出所有已知状态的估计值，

不断从堆顶出选出 当前代价+未来估价 最小的状态进行扩展。

注意，估价函数一定要满足以下准则 ~~（核能预警）~~ ：

设估价函数值为 $ f(state)$
设未来实际求出的最小值为 $ g(state)$
一定要满足 $f(state)<=d(state)$

~~这个规律显而易见吧。~~

这种**带有估价函数的优先队列bfs就称为a*算法**。

例题1

第k短路 poj2449

思路很巧~~（好像a*的思路都很巧）~~

简单说就是讲终点到这个节点的最短路作为估价函数（显然最短路<第k短路）

代码如下：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define n 1010
#define m 100010
using namespace std;

int n,m,s,t,k;
int dis[n],head[n],sum[n],cnt=0;
bool use[n];
struct node{
    int to,val,next;
}edge[m];
priority_queue<pair<int,int> >q;
struct astar{
    int x,h,g;
    friend bool operator < (astar a,astar b){
        return a.h+a.g>b.h+b.g;
    }
};
priority_queue<astar>qq;
vector<node>v[n];

void addedge(int x,int y,int z){
    cnt++;
    edge[cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].val=z;
    head[x]=cnt;
    v[y].push_back((node){x,z,0});
    return;
}

void dij(){
    memset(use,false,sizeof(use));
    memset(dis,0x3f,sizeof(dis));
    dis[t]=0;
    q.push(make_pair(0,t));
    
    while(!q.empty()){
        int now=q.top().second;
        q.pop();
        if(use[now]) continue;
        use[now]=true;
        for(int i=0;i<v[now].size();i++){
            int y=v[now][i].to;
            int z=v[now][i].val;
            if(dis[y]>dis[now]+z){
                dis[y]=dis[now]+z;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
    return;
}

void a_star(){
    memset(sum,0,sizeof(sum));
    qq.push((astar){s,0,0});
    
    while(!qq.empty()){
        astar now=qq.top();
        qq.pop();
        sum[now.x]++;
        if(sum[now.x]==k && now.x==t){
            printf("%d\n",now.h);
            return;
        }
        if(sum[now.x]>k) continue;
        for(int i=head[now.x];i;i=edge[i].next){
            int y=edge[i].to;
            int z=edge[i].val;
            //printf("%d %d\n",y,dis[y]+now.dist+z);
            qq.push((astar){y,now.h+z,dis[y]});
        }
    }
    printf("-1\n");
    return;
}

int main(){
    scanf("%d %d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&c);
        addedge(a,b,c);
    }
    scanf("%d %d %d",&s,&t,&k);
    dij();
    if(s==t) k++;
    a_star();
    return 0;
}

例题2

八数码难题

我好像是用双向bfs做的，但是a*跑得更快（自己啃书吧）

#include<algorithm>
#include<cstdio>
#include<queue>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;

int a,b=123804765,p[5][5],fx,fy;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
queue<int>q;
map<int,int>flag;
map<int,int>ans;

void to_juzhen(int now){
    for(int i=3;i>=1;i--){
        for(int j=3;j>=1;j--){
            p[i][j]=now%10;now/=10;
            if(p[i][j]==0){
                fx=i;fy=j;
            } 
        }
    }
    return;
}

int to_shulie(){
    int x=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            x=x*10+p[i][j];
        }
    }
    return x;
}

void bfs(){
    q.push(a);q.push(b);
    flag[a]=1;flag[b]=2;
    ans[a]=ans[b]=1;
    
    while(!q.empty()){
        int now,cur=q.front();
        now=cur;
        q.pop();
        
        to_juzhen(now);
        
        for(int i=1;i<=4;i++){
            int gx=fx+dx[i];
            int gy=fy+dy[i];
            if(gx>3||gx<1||gy>3||gy<1) continue;
            swap(p[fx][fy],p[gx][gy]);
            
            now=to_shulie();
            
            if(flag[now]==flag[cur]){
                swap(p[fx][fy],p[gx][gy]);
                continue;
            }
            
            if(flag[now]+flag[cur]==3){
                printf("%d\n",ans[now]+ans[cur]-1);
                return;
            }
            
            flag[now]=flag[cur];
            ans[now]=ans[cur]+1;
            q.push(now);
            swap(p[fx][fy],p[gx][gy]);
        }
    }
    return;
}

int main(){
    scanf("%d",&a);
    if(a==b){
        printf("0\n");
        return 0;
    }
    bfs();
    return 0;
}

六、ida*算法

ida*简述

简单说，\[ ida*=id+a* \] （废话）

核心一句话：若当前深度+未来估计步数>深度限制，立即回溯 。

例题

booksort poj3460

简单的很，具体思路回原文。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define maxn 20
using namespace std;

int n,a[maxn],flag,deep;

void book_swap(int x,int y,int z){
    int p[maxn],tot=x;
    for(int i=y+1;i<=z;i++) p[tot++]=a[i];
    for(int i=x;i<=y;i++) p[tot++]=a[i];
    for(int i=x;i<=z;i++) a[i]=p[i];
    return;
}

int h(){
    int sum=0;
    for(int i=1;i<n;i++){
        if(a[i+1]!=a[i]+1) sum++;
    }
    if(a[n]!=n) sum++;
    return ceil(((double)sum/3));
}

void dfs(int step){
    if(step+h()>deep||flag) return;
    if(h()==0){
        flag=true;
        printf("%d\n",step);
        return;
    }

    for(int i=1;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=j+1;k<=n;k++){
                book_swap(i,j,k);
                dfs(step+1);
                if(flag) return;
                book_swap(i,i+k-j-1,k);
            }
        }
    }
    return;
}

void ida(){
    deep=0;
    flag=false;
    while(1){
        deep++;
        dfs(0);
        if(flag) break;
        if(deep==4){
            printf("5 or more\n");
            break;
        }
    }
    return;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        ida();
    }
    return 0;
}

七、总结与习题

总结

dfs -> 剪枝 -> id、双向 -> ida*

bfs -> 双端队列、优先队列、双向 -> a*

搜索题主要考验代码能力，也是增强代码能力的好方法，但在 $noip$ 以上的比赛中，并不是主要考点...

学好搜索，相信你可以 暴力踩标算，打表出省一 。

习题

靶形数独

#include<algorithm>
#include<cstdio>
#include<queue>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;

int a,b=123804765,p[5][5],fx,fy;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
queue<int>q;
map<int,int>flag;
map<int,int>ans;

void to_juzhen(int now){
    for(int i=3;i>=1;i--){
        for(int j=3;j>=1;j--){
            p[i][j]=now%10;now/=10;
            if(p[i][j]==0){
                fx=i;fy=j;
            } 
        }
    }
    return;
}

int to_shulie(){
    int x=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            x=x*10+p[i][j];
        }
    }
    return x;
}

void bfs(){
    q.push(a);q.push(b);
    flag[a]=1;flag[b]=2;
    ans[a]=ans[b]=1;
    
    while(!q.empty()){
        int now,cur=q.front();
        now=cur;
        q.pop();
        
        to_juzhen(now);
        
        for(int i=1;i<=4;i++){
            int gx=fx+dx[i];
            int gy=fy+dy[i];
            if(gx>3||gx<1||gy>3||gy<1) continue;
            swap(p[fx][fy],p[gx][gy]);
            
            now=to_shulie();
            
            if(flag[now]==flag[cur]){
                swap(p[fx][fy],p[gx][gy]);
                continue;
            }
            
            if(flag[now]+flag[cur]==3){
                printf("%d\n",ans[now]+ans[cur]-1);
                return;
            }
            
            flag[now]=flag[cur];
            ans[now]=ans[cur]+1;
            q.push(now);
            swap(p[fx][fy],p[gx][gy]);
        }
    }
    return;
}

int main(){
    scanf("%d",&a);
    if(a==b){
        printf("0\n");
        return 0;
    }
    bfs();
    return 0;
}

食虫算

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int n,a[30],b[30],c[30];
int num[30],id[30],sum=0;
char aa[30],bb[30],cc[30];
bool use[30];

void get(int x){
    if(!use[x]){
        use[x]=true;
        id[sum++]=x;
    }
    return;
}

bool check(){
    for(int i=n,p=0;i>=1;i--){
        int a=num[a[i]],b=num[b[i]],c=num[c[i]];
        if((a+b+p)%n!=c) return false;
        p=(a+b+p)/n;
    }
    return true;
}

void print(){
    for(int i=1;i<=n;i++) printf("%d ",num[i]);
    exit(0);
}

bool cut_down(){
    if(num[a[1]]+num[b[1]]>=n) return true;
    for(int i=n;i>=1;i--){
        int a=num[a[i]],b=num[b[i]],c=num[c[i]];
        if(a==-1||b==-1||c==-1) continue;
        if((a+b)%n!=c&&(a+b+1)%n!=c) return true;
    }
    return false;
}

void dfs(int x){
    //for(int i=1;i<=n;i++) printf("%d ",num[i]);
    //printf("\n");
    if(cut_down()) return;
    if(x==n){
        if(check()) print();
        return;
    }
    
    for(int i=n-1;i>=0;i--){
        if(!use[i]){
            num[id[x]]=i;
            use[i]=true;
            dfs(x+1);
            num[id[x]]=-1;
            use[i]=false;
        }
    }
    return;
}

int main(){
    scanf("%d",&n);
    cin>>aa>>bb>>cc;
    for(int i=1;i<=n;i++){
        a[i]=aa[i-1]-'a'+1;
        b[i]=bb[i-1]-'a'+1;
        c[i]=cc[i-1]-'a'+1;
        num[i]=-1;
    }
    
    memset(use,false,sizeof(use));
    for(int i=n;i>=1;i--){
        get(a[i]);get(b[i]);get(c[i]);
    }
    memset(use,false,sizeof(use));
    dfs(0);
    return 0;
}

mayan 游戏

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;

int deep,map[10][10],ans[10][5];
int last[10][10][10];

void copy(int x){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            last[x][i][j]=map[i][j];
        }
    }
    return;
}

void build(){
    for(int i=1;i<=5;i++){
        int sum=0;
        for(int j=1;j<=7;j++){
            if(!map[i][j]) sum++;
            else{
                if(!sum) continue;
                map[i][j-sum]=map[i][j];
                map[i][j]=0;
            }
        }
    }
    return;
}
bool can[10][10];
bool delet(){
    bool flag=false;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){
                can[i][j]=true;can[i-1][j]=true;can[i+1][j]=true;flag=true;
            }
            if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){
                can[i][j]=true;can[i][j-1]=true;can[i][j+1]=true;flag=true;
            }
        }
    }
    if(!flag) return false;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(can[i][j]){
            map[i][j]=0;
            can[i][j]=false;
            }
        }
    }
    return true;
}

void change(int i,int j,int x){
    int tmp=map[i][j];
    map[i][j]=map[i+x][j];
    map[i+x][j]=tmp;
    build();
    while(delet())build();//我就把while写成if了，调了我三个小时...
}

bool chck(){
    for(int i=1;i<=5;i++){
        if(map[i][1]) return false;
    }
    return true;
}

void dfs(int x){
    if(chck()){
        for(int i=1;i<=deep;i++){
            if(i!=1)printf("\n");
            for(int j=1;j<=3;j++)
            printf("%d ",ans[i][j]);
        }
        exit(0);
    }
    if(x==deep+1)return;
    copy(x);
    for(int i=1;i<=5;i++)
        for(int j=1;j<=7;j++){
            if(map[i][j]){
                if(i+1<=5&&map[i][j]!=map[i+1][j]){
                change(i,j,1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
                dfs(x+1);
                for(int i=1;i<=5;i++)
                    for(int j=1;j<=7;j++)
                    map[i][j]=last[x][i][j];
                ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
            }
            if(i-1>=1&&map[i-1][j]==0){
                change(i,j,-1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
                dfs(x+1);
                for(int i=1;i<=5;i++)
                    for(int j=1;j<=7;j++)
                    map[i][j]=last[x][i][j];
                ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
            }
            }
        }
}

int main(){
    int p;
    scanf("%d",&deep);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=8;j++){
            scanf("%d",&p);
            if(!p) break;
            map[i][j]=p;
        }
    }
    memset(ans,-1,sizeof(ans));
    dfs(1);
    printf("-1\n");
    return 0;
}

武士风度的牛

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 160 
using namespace std;

int n,m,sx,sy,ex,ey;
int dx[10]={0,2,2,1,1,-1,-1,-2,-2};
int dy[10]={0,1,-1,2,-2,2,-2,1,-1};
int dis[maxn][maxn];
char a[maxn][maxn];
struct node{
    int x,y;
};
queue<node>q;

void bfs(){
    q.push((node){sx,sy});
    memset(dis,-1,sizeof(dis));
    dis[sx][sy]=0;
    
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=1;i<=8;i++){
            int fx=dx[i]+now.x;
            int fy=dy[i]+now.y;
            if(fx<1 || fx>n || fy<1 || fy>m || dis[fx][fy]!=-1 || a[fx][fy]=='*') continue;
            dis[fx][fy]=dis[now.x][now.y]+1;
            if(fx==ex && fy==ey){
                printf("%d\n",dis[fx][fy]);
                return;
            }
            q.push((node){fx,fy});
        }
    }
}

int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++){
            if(a[i][j]=='k'){sx=i;sy=j;}
            else if(a[i][j]=='h'){ex=i;ey=j;}
        }
    }
    bfs();
    return 0;
}

乳草的入侵

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define maxn 110
using namespace std;

int n,m,sx,sy,sum=0,tot=1;
int dx[10]={0,1,-1,0,0,1,1,-1,-1};
int dy[10]={0,0,0,1,-1,1,-1,1,-1};
int dis[maxn][maxn];
char a[maxn][maxn];
queue<pair<int,int> >q;

void bfs(){
    memset(dis,-1,sizeof(dis));
    dis[sx][sy]=0;
    q.push(make_pair(sx,sy));
    
    while(!q.empty()){
        int nowx=q.front().first;
        int nowy=q.front().second;
        q.pop();
        for(int i=1;i<=8;i++){
            int fx=nowx+dx[i];
            int fy=nowy+dy[i];
            if(fx<1 || fx>n || fy<1 || fy>m || dis[fx][fy]!=-1 || a[fx][fy]=='*') continue;
            dis[fx][fy]=dis[nowx][nowy]+1;
            tot++;
            if(tot==sum){
                printf("%d\n",dis[fx][fy]);
                return;
            }
            q.push(make_pair(fx,fy));
        }
    }
    return;
}

int main(){
    int p,q;
    scanf("%d %d %d %d",&m,&n,&p,&q);
    sx=n-q+1;sy=p;
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++){
            if(a[i][j]!='*'){
                sum++;
            }
        }
    }
    //printf("%d\n",sum);
    bfs();
    return 0;
}

字串变换

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<iostream>
#include<cmath>
#define maxn 9999999
using namespace std;

string a,b,change1[10],change2[10];
map<string,bool>v1;
map<string,int>v2;
int t=1,d=1,ans=maxn;

void dfs(string now,int step){
    if(step>d) return;
    if(now==b){
        ans=min(ans,step);
        return;
    }
    if(v1[now]){
        if(step>=v2[now]) return;
    }
    v1[now]=true;v2[now]=step;
    int f;
    string x;
    for(int i=1;i<=t;i++){
        f=-1;
        while(1){
            f=now.find(change1[i],f+1);
            if(f==-1) break;
            x=now;
            x.erase(f,change1[i].size());
            x.insert(f,change2[i]);
            dfs(x,step+1);
        }
    }
    return; 
}

int main(){
    cin>>a>>b;
    while(cin>>change1[t]>>change2[t]) t++;
    t--;
    
    while(ans==maxn){
        dfs(a,0);
        v1.clear();v2.clear();
        d++;
        if(d>10) break;
    }
    
    if(ans==maxn){
        printf("no answer!\n");
        return 0;
    }
    printf("%d\n",ans);
    return 0;
}

骑士精神

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int t,a[10][10];
bool flag;//,chong[10][10];
int dx[10]={0,1,1,-1,-1,2,2,-2,-2};
int dy[10]={0,2,-2,2,-2,1,-1,1,-1};
int f[10][10]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,2,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
};

int check(){
    int sum=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            if(f[i][j]!=a[i][j]) sum++;
        }
    }
    return sum;
}

void dfs(int xx,int yy,int step,int maxstep){
    if(flag) return;
    if(step==maxstep){
        if(!check()) flag=true;
        return;
    }
    //if(step+check()/2>maxstep) return;
    
    for(int i=1;i<=8;i++){
        int gx=xx+dx[i];
        int gy=yy+dy[i];
        if(gx>5||gx<1||gy>5||gy<1) continue;
        //chong[gx][gy]=true;
        swap(a[xx][yy],a[gx][gy]);
        if(check()+step<=maxstep) dfs(gx,gy,step+1,maxstep);
        swap(a[xx][yy],a[gx][gy]);
    }
    return;
}

int main(){
    scanf("%d",&t);
    while(t--){
        char ch;
        int xx,yy;
        flag=false;
        
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                cin>>ch;
                if(ch=='*') {a[i][j]=2;xx=i;yy=j;}
                else a[i][j]=ch-'0';
            }
        }
        
        if(!check()) {printf("0\n");continue;}
        
        for(int i=1;i<=15;i++){
            //memset(chong,false,sizeof(chong));
            dfs(xx,yy,0,i);
            if(flag) {printf("%d\n",i);break;}
        }
        
        if(!flag) printf("-1\n"); 
    }
    return 0;
}

结语

终于写完了，好开心。

全篇唯一参考资料：《算法竞赛进阶指南》

再见。

上一篇：白萝卜好处有哪些，吃白萝卜需要注意什么

下一篇：利用 wave 库对音频进行格式处理

搜索

搜索

前言

一、树与图的遍历

树与图的dfs遍历、树的dfs序、深度和重心

遍历

树的深度

树的重心

图的连通块的划分

树与图的bfs遍历、拓扑排序

遍历

拓扑排序

例题

可达性问题

二、深度优先搜索及剪枝

dfs简述

dfs例题

小猫爬山

sudoku

剪枝

剪枝例题

sticks

生日蛋糕

三、迭代加深及dfs常见优化

迭代加深

例题

岳麓山打水

双向搜索

四、广度优先搜索及其优化

广度优先搜索

例题

bloxorz

pushing boxes

双端队列bfs

优先队列bfs

双向广搜

五、a*算法

a*简述

例题1

例题2

六、ida*算法

ida*简述

例题

七、总结与习题

总结

习题

靶形数独

食虫算

mayan 游戏

武士风度的牛

乳草的入侵

字串变换

骑士精神

结语

xmind思维导图怎么搜索内容?

Win10系统搜索框怎么从底部移到屏幕顶部?

详解jQuery如何实现模糊搜索

搜索引擎优化的内容包括哪些方面，搜索引擎排行大全

Java开发工具Eclipse使用技巧全局搜索和更替

Android实现搜索保存历史记录功能

用搜狗微信公众号搜索功能进行快速搜索

outlook中的即时搜索怎么关闭?

Java创建二叉搜索树,实现搜索,插入,删除的操作实例

Android拨号盘 支持T9搜索和号码搜索等拨号盘案例

Android拨号盘支持T9搜索和号码搜索等拨号盘案例