Abbott 的复仇（Abbott's Revenge，ACM|IPPC World Finals 2000, UVa 816)

78 阅读 0 评论 52 点赞

我是靠谱客的博主彪壮自行车，最近开发中收集的这篇文章主要介绍Abbott 的复仇（Abbott's Revenge，ACM|IPPC World Finals 2000, UVa 816)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

<pre name="code" class="cpp">//算法竞赛入门经典中一道经典的用BFS求最短路径例题
//2015/01/30

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef struct node		//结点数据 
{
	node(){}
	node(int row,int col,int d):r(row),c(col),dir(d){}
	int r;
	int c;
	int dir;	//横坐标，纵坐标，移动方向 
}Node;

int N=0,E=1,S=2,W=3;	//北东南西
int F=0,L=1,R=2;	//直行，左转，右转

int r0=3,c0=1,dir0=N;	//出发点 
int r1=2,c1=1,dir1=N;	//起始点（第二个）
int r2=3,c2=3;	//终点 

bool has_edge[4][4][4][3];	//下一步能走的方向

int d[4][4][4];	//初始点到当前点的最短距离 
Node p[4][4][4];	//当前结点的前驱 

const int dr[]={-1,0,1,0};	//下标由NESW决定 
const int dc[]={0,1,0,-1};

Node walk(const Node& u,int turn)	//根据当前结点，得到下一步的结点 
{
	int dir=u.dir;	//当前移动方向
	if(turn==1)dir=(dir+3)%4;	//左转
	if(turn==2) dir=(dir+1)%4;	//右转
	//turn=0时直行没有变化
	return Node(u.r+dr[dir],u.c+dc[dir],dir);		
}
bool inside(int r,int c)	//判断是否出界 
{
	if(r<=0||r>3||c<=0||c>3)return false;
	else return true;		
}
//打印路径
void print_ans(Node u)
{
	vector<Node> nodes;
	for(;;){
		nodes.push_back(u);
		if(d[u.r][u.c][u.dir]==0)break;	//起始点
		u=p[u.r][u.c][u.dir];	//前驱 
	}
	nodes.push_back(Node(r0,c0,dir0));	//出发点
	int cnt=0;	//打印解，每行10个 
	for(int i=nodes.size()-1;i>=0;i--)
	{
		if(cnt%10!=0)cout<<" ";
		cout<<"("<<nodes[i].r<<nodes[i].c<<")";	
		if(++cnt%10==0)cout<<"n";
	} 
} 
//图的BFS主过程 
void solve()
{
	queue<Node> q;
	memset(d,-1,sizeof(d));
	Node u(r1,c1,dir1);
	d[u.r][u.c][u.dir]=0;
	q.push(u);
	while(!q.empty())
	{
		Node u=q.front();q.pop();
		if(u.r==r2&&u.c==c2){
			print_ans(u);return;
		}
		for(int i=0;i<3;i++)	//直行，左转，右转 
		{
			Node v=walk(u,i);
			if(has_edge[u.r][u.c][u.dir][i]&&inside(v.r,v.c)&&d[v.r][v.c][v.dir]<0)
			{
				d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
				p[v.r][v.c][v.dir]=u;
				q.push(v);
			}
		}
	}
	cout<<"No Solution Possible!"<<endl;
}

int main()
{
	memset(has_edge, 0, sizeof(has_edge));
	//设置每个点可以移动的方向 
	has_edge[3][1][N][F] = true;
	has_edge[2][1][N][F] = true; 
	has_edge[2][1][S][L] = true; 
	has_edge[2][1][W][R] = true; 
	has_edge[1][1][N][R] = true; 
	has_edge[1][1][W][L] = true; 
	has_edge[1][2][E][R] = true; 
	has_edge[1][2][W][F] = true; 
	has_edge[1][2][W][L] = true; 
	has_edge[1][2][N][R] = true; 
	has_edge[2][2][E][F] = true; 
	has_edge[2][2][E][L] = true; 
	has_edge[2][2][S][L] = true; 
	has_edge[2][2][W][F] = true; 
	has_edge[1][3][E][R] = true; 
	has_edge[1][3][N][L] = true;
	has_edge[2][3][E][L] = true; 
	has_edge[2][3][S][F] = true; 
	has_edge[2][3][S][R] = true; 
	has_edge[3][3][S][F] = true; 
	solve();
	return 0;
}