目录

• • • 树与图的dfs遍历、树的dfs序、深度和重心
    • 树与图的bfs遍历、拓扑排序
  • • dfs简述
    • dfs例题
  • 三、迭代加深及dfs常见优化
  • • 双端队列bfs
    • 优先队列bfs
  • 五、a*算法
    • a*简述
  • 六、ida*算法
    • ida*简述

搜索

前言

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

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

其实就是在本书基础上加上自己的理解（作为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是一种按照层次顺序遍历的算法，它具有以下两个重要性质：

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

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

拓扑排序

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

1. 每个顶点出现且只出现一次。

2. 若存在一条从顶点 a 到顶点 b 的路径，那么在序列中顶点 a 出现在顶点 b 的前面。

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

1. 找到图中入度为0的点（即没有边以它为终点的点），把它放入队列。
2. 取出队列中的点，输出之，删掉与之相邻的边，并把那些边的终点的入度减1。
3. 重复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;
}

剪枝

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

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

常见的剪枝方法如下：

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

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;
}

结语

终于写完了，好开心。

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

再见。