当前位置：自学咖网 > 技术教程 > 编程最新 > UVA439 骑士的移动
wenwen 编程最新

UVA439 骑士的移动

UVA439 骑士的移动 [编程语言教程]

UVA439 骑士的移动

之所以这道题我要写题解，是因为解题的过程中我采用了多种方法（不严谨的说，基本写完了搜索里的所有技巧）——BFS，IDA* ，A*，双向DFS。

这个过程很值得品味参考，于我来说也是一次不可多得的学习。

BFS

这道题的BFS思路是比较显然的，代码实现上也不算特别难。

#include<bits/stdc++.h>

int max_dep;
int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;


namespace WalkerV {
	void Init() {
		max_dep=0;
		memset(f,0,sizeof(f));
		return;
	}

	double Estimate_Function(int x1,int y1,int x2,int y2) {
		return std::ceil((std::abs(x1-x2)+std::abs(y1-y2))/3.0);
	}

	bool IDDFS(int x,int y,int dep) {
		if(dep==max_dep) {
			if(x==t.x&&y==t.y) {
				f[x][y]=dep;
				return true;
			}
			else {
				return false;
			}
		}
		//printf("x:%d y:%d g(x):%d f(x):%.1f
",x,y,dep,Estimate_Function(x,y,t.x,t.y));
		for(int i=1;i<=8;i++) {
			if(x+dx[i]>=1&&x+dx[i]<=8&&y+dy[i]>=1&&y+dy[i]<=8&&!f[x+dx[i]][y+dy[i]]) {
				//printf("move to %d %d, g:%d f:%.1f max_dep:%d
",x+dx[i],y+dy[i],dep+1,Estimate_Function(x+dx[i],y+dy[i],t.x,t.y),max_dep);
				if(dep+1+Estimate_Function(x+dx[i],y+dy[i],t.x,t.y)>max_dep) { //g(x):dep+1 f(x):ceil(M_Dis/3)
					//printf("cut
");
					continue;
				}
				if(IDDFS(x+dx[i],y+dy[i],dep+1)) {
					return true;
				}
			}
		}
		return false;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		while(!IDDFS(s.x,s.y,0)) {
			memset(f,0,sizeof(f));
			max_dep++;
			//printf("max_dep:%d
",max_dep);
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.
",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}

}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

IDA*

然后便是IDA*。

如果你问我为什么不先写A*，因为这份代码的重点是迭代加深，也就是ID(Iterative Deepening)。但单打一份迭代加深的DFS意义不大，所以就选择用IDA*。而且从各种角度来说，IDA*都比A*要优秀一些。

但是这份代码应该说是几份代码我调得最痛苦的一份（大概前前后后修了三四个小时左右），最后的关键错误还是落在了估价函数上。

有必要说一下估价函数的设计：因为是马在棋盘上的移动，所以考虑曼哈顿距离。我们知道马每次移动的曼和顿距离为$3$，所以乐观估计应当是当前位置到终点的曼哈顿距离除以$3$并向上取整。

#include<bits/stdc++.h>

int max_dep;
int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;


namespace WalkerV {
	void Init() {
		max_dep=0;
		memset(f,0,sizeof(f));
		return;
	}

	double Estimate_Function(int x1,int y1,int x2,int y2) {
		return std::ceil((std::abs(x1-x2)+std::abs(y1-y2))/3.0);
	}

	bool IDDFS(int x,int y,int dep) {
		if(dep==max_dep) {
			if(x==t.x&&y==t.y) {
				f[x][y]=dep;
				return true;
			}
			else {
				return false;
			}
		}
		//printf("x:%d y:%d g(x):%d f(x):%.1f
",x,y,dep,Estimate_Function(x,y,t.x,t.y));
		for(int i=1;i<=8;i++) {
			if(x+dx[i]>=1&&x+dx[i]<=8&&y+dy[i]>=1&&y+dy[i]<=8&&!f[x+dx[i]][y+dy[i]]) {
				//printf("move to %d %d, g:%d f:%.1f max_dep:%d
",x+dx[i],y+dy[i],dep+1,Estimate_Function(x+dx[i],y+dy[i],t.x,t.y),max_dep);
				if(dep+1+Estimate_Function(x+dx[i],y+dy[i],t.x,t.y)>max_dep) { //g(x):dep+1 f(x):ceil(M_Dis/3)
					//printf("cut
");
					continue;
				}
				if(IDDFS(x+dx[i],y+dy[i],dep+1)) {
					return true;
				}
			}
		}
		return false;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		while(!IDDFS(s.x,s.y,0)) {
			memset(f,0,sizeof(f));
			max_dep++;
			//printf("max_dep:%d
",max_dep);
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.
",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}

}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

A*

在有了BFS和IDA*的基础上，A*就显得非常容易了。

估价函数的设计与IDA*是一致的。

#include<bits/stdc++.h>

int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
	double est;
	friend bool operator < (node a,node b) {
		return a.est>b.est;
	}
}s,t;

namespace WalkerV {
	void Init() {
		memset(f,0,sizeof(f));
		return;
	}
	
	double Estimate_Function(int x,int y) {
		return std::ceil((std::abs(x-t.x)+std::abs(y-t.y))/3.0);
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘,0},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘,0};
		s.est=Estimate_Function(s.x,s.y);
		std::priority_queue<node> q;
		q.push(s),f[s.x][s.y]=0;
		while(q.size()) {
			node k=q.top();
			q.pop();
			if(k.x==t.x&&k.y==t.y) {
				return;
			}
			for(int i=1;i<=8;i++) {
				if(k.x+dx[i]>=1&&k.x+dx[i]<=8&&k.y+dy[i]>=1&&k.y+dy[i]<=8&&!f[k.x+dx[i]][k.y+dy[i]]) {
					f[k.x+dx[i]][k.y+dy[i]]=f[k.x][k.y]+1;
					q.push((node){k.x+dx[i],k.y+dy[i],f[k.x+dx[i]][k.y+dy[i]]+Estimate_Function(k.x+dx[i],k.y+dy[i])});
				}
			}
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.
",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}
}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

双向BFS

对于这题，由于我们已经知道搜索的初态和末态，所以既可以从初态搜到末态，也可以从末态搜到初态。

在此基础上，双向BFS的思路也就呼之欲出了——从初态和末态同时往中间搜索（具体实现应当是正反各搜一轮）。

由于我们使用的是BFS，所以在轮流搜索的时候但凡有一个状态被两边都搜索到了（也就是说第一个被两边都搜索到的状态），那么这个状态到初态和末态的路径和就是答案（正确性显然）。

此外，在代码中需要注意的有如下两点：

  • 末态的初值应赋为$1$，因为在实际的移动中，是需要$1$步才能走到终点的。

  • 起点和终点重合需要特判，不然程序就会处理为需要$2$步才能到（反复横跳一次）。

说句闲话，其实中间两个队列的实现那里，如果用typedef写会更好看一些，但是可读性会大大降低（逃

#include<bits/stdc++.h>

int ans;
int f1[10][10],f2[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;

namespace WalkerV {
	void Init() {
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		return;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		if(s.x==t.x&&s.y==t.y) {
			ans=0;
			return;
		}
		std::queue<node> q1,q2;
		q1.push(s),f1[s.x][s.y]=0;
		q2.push(t),f2[t.x][t.y]=1;
		while(q1.size()||q2.size()) {
			bool flag;
			node k;
			if(q1.size()<=q2.size()) { //edit q1
				k=q1.front();
				q1.pop();
				flag=true;
			}
			else { //edit q2
				k=q2.front();
				q2.pop();
				flag=false;
			}
			for(int i=1;i<=8;i++) {
				if(k.x+dx[i]>=1&&k.x+dx[i]<=8&&k.y+dy[i]>=1&&k.y+dy[i]<=8) {
					switch(flag) {
						case true:
							if(f2[k.x+dx[i]][k.y+dy[i]]) {
								ans=f1[k.x][k.y]+f2[k.x+dx[i]][k.y+dy[i]];
								return;
							}
							f1[k.x+dx[i]][k.y+dy[i]]=f1[k.x][k.y]+1;
							q1.push((node){k.x+dx[i],k.y+dy[i]});
							break;
						case false:
							if(f1[k.x+dx[i]][k.y+dy[i]]) {
								ans=f2[k.x][k.y]+f1[k.x+dx[i]][k.y+dy[i]];
								return;
							}
							f2[k.x+dx[i]][k.y+dy[i]]=f2[k.x][k.y]+1;
							q2.push((node){k.x+dx[i],k.y+dy[i]});
							break;
					}				
				}
			}
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.
",op,ed,ans);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}
}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

说点别的

这次这道题码下来，还算是收获颇丰。谁会想到，一个学了两年多OI的人，直到这道题才算是摸透了上面四种算法（包括BFS）。

此外，在写代码的时候，感觉到(ID)A*是真正优秀的算法。这不仅体现在它的运行时间上，而是说这种算法是最贴近人类行为的。作为人类，我们在解决问题中面临多种方式时，一定会略作估计并选取最优的方式进行尝试。可能这也是启发式算法被广泛运用到人工智能里的原因，毕竟我们人类定义的人工智能就是与人类智能所相似的机器。

UVA439 骑士的移动

原文地址：https://www.cnblogs.com/luoshui-tianyi/p/13912507.html

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » UVA439 骑士的移动

wen 普通

分享到：

相关推荐

三种PHP环境下文件加密的流程

php文件加密操作流程 　　不同的PHP调试环境，加密略有差异。 下面主要介绍windows下phpstudy2018、xampp及phpstudy-pro三种环境的php文件加密。 　　01不同环境的通用流程 　　1....

数论笔记

♠ use C++11 倍数 若 (a,b,k in mathbb N)，且 (a imes k=b)，那么 (b) 是 (a) 的倍数，称 (a) 整除 (b)，记作 (a mid b)。 ([1,n]) 中 (x i...

Python发送的邮件设置收件人隐藏与显示

1.代码说明 在实际的使用中，有些邮件我们希望收件人可以看到还有那些人可以收到此邮件，但有些邮件相反，例如含有一些较敏感的信息时，希望收件人都是隐藏的。一般我们可以在邮件配置文件smtp_conig.py中设置，下面是为...

用Python实现一个Picgo图床工具

PyPicGo PyPicGo 是一款图床工具,是PicGo是Python版实现，并支持各种插件自定义插件，目前PyPicGo自带了gitee、github、SM.MS和七牛云图传，以及rename、notify和typ...

docker安装mysql完美教程(建议收藏!)

目录 快速完成 详细步骤  首先搜索镜像 拉取镜像 创建容器（运行镜像） 进入容器 本地使用连接工具连接 修改字符集 使用容器数据卷挂载mysql数据、配置文件、日志 创建mysql的配置文件 总结