搜索

0
16

搜索

目录

  • 搜索
    • 前言
    • 一、树与图的遍历
      • 树与图的DFS遍历、树的DFS序、深度和重心
        • 遍历
        • 树的深度
        • 树的重心
        • 图的连通块的划分
      • 树与图的BFS遍历、拓扑排序
        • 遍历
        • 拓扑排序
      • 例题
        • 可达性问题
    • 二、深度优先搜索及剪枝
      • DFS简述
      • DFS例题
        • 小猫爬山
        • Sudoku
      • 剪枝
      • 剪枝例题
        • Sticks
        • 生日蛋糕
    • 三、迭代加深及DFS常见优化
      • 迭代加深
      • 例题
        • 岳麓山打水
      • 双向搜索
    • 四、广度优先搜索及其优化
      • 广度优先搜索
      • 例题
        • Bloxorz
        • Pushing Boxes
      • 双端队列BFS
      • 优先队列BFS
      • 双向广搜
    • 五、A*算法
      • A*简述
      • 例题1
      • 例题2
    • 六、IDA*算法
      • IDA*简述
      • 例题
    • 七、总结与习题
      • 总结
      • 习题
        • 靶形数独
        • 食虫算
        • Mayan 游戏
        • 武士风度的牛
        • 乳草的入侵
        • 字串变换
        • 骑士精神
    • 结语

前言

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

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

其实就是在本书基础上加上自己的理解(作为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;
}

结语

终于写完了,好开心。

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

再见。

<

发布回复

请输入评论!
请输入你的名字