例题6-14 Abbott's Revenge Uva816

56 阅读 0 评论 37 点赞

我是靠谱客的博主虚幻金毛，最近开发中收集的这篇文章主要介绍例题6-14 Abbott's Revenge Uva816，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目连接：https://vjudge.net/problem/UVA-816

题意：有一个 9 * 9 的交叉点的迷宫。输入起点，离开起点时的朝向和终点，求最短路（多解时任意一个输出即可）。进入一个交叉点的方向（用NEWS表示不同方向）不同时，允许出去的方向也不相同。例如：1 2 WLF NR ER * 表示如果进去时朝W（左），可以左转（L）或直行（F），如果朝N只能右转（R）如果朝E也只能右转。* 表示这个点的描述结束啦！

　　　　输入有：起点的坐标，朝向，终点的坐标。然后是各个坐标，和各个坐标点的情况（进去方向和可以出去的方向）以*号表示各个坐标点描述的结束。

题目分析：本题和普通的迷宫在本质上是一样的，但是由于“朝向”也起了关键的作用，所以需要一个三元组（r，c, dir）表示位于（r， c）面朝dir 的状态。假设入口位置为（r0，c0）朝向为dir ，则初始状态并不是（r0， c0， dir），而是（r1， c1， dir）因为开始时他别无选择，只有一个规定的方向。其中，（r1， c1）是沿着方向dir走一步之后的坐标， dir刚好是他进入该点时的朝向。此处用d[r][c][dir]表示初始状态到（r， c， dir）的最短路长度，并且用 p[r][c][dir]保存了状态（r， c， dir）在BFS树中的父结点。

思路：简单BFS应用，但是细节很多，格式神烦。

Code：

#include <bits/stdc++.h>
using namespace std;
const int AX = 20;
int d[AX][AX][4];
int has_edge[AX][AX][AX][AX];
int start_r , start_c , end_r , end_c;
int s_x , s_y ,s_dir;
char start_dir[5]  ;
string name;
struct Node
{
	int x , y ;
	int dir;
	Node(){};
	Node( int x_ , int y_ , int dir_ ) { x = x_ ; y = y_; dir = dir_; }
}start;
Node p[AX][AX][4];

const char* dirs = "NESW";
const char* turns = "FLR";
int dir_id(char ch) { return strchr(dirs,ch)-dirs; }
int turns_id(char ch) { return strchr(turns,ch)-turns; }

const int dr[] = { -1, 0, 1, 0 };
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;
	return Node( u.x + dr[dir] , u.y + dc[dir] , dir );
}

bool inside( int x , int y ){
	if( x >= 1 && x <= 9 && y >= 1 && y <= 9 ){
		return true;
	}else return false;
}

void print( Node u ){ 
	std::vector<Node> v;
	while( true ){
		v.push_back(u);
		if( !d[u.x][u.y][u.dir] )  break;
		u = p[u.x][u.y][u.dir];
	}
	int cnt = 0;
	cout << name << endl;
	v.push_back(Node(s_x,s_y,s_dir));
	for( int i = v.size() - 1 ; i >= 0 ; i-- ){
		if( cnt % 10 == 0 ) cout << " " ;
		cout << " (" << v[i].x << ',' << v[i].y << ")";
		if( ++cnt % 10 == 0 ) cout << endl;
	}
	if( v.size() % 10 != 0 ) cout << endl;
}

void BFS( ){
	queue<Node>q; 
	memset(d,-1,sizeof(d));
	d[start.x][start.y][start.dir] = 0;
	q.push(start);
	while( !q.empty() ){
		Node u = q.front();
		q.pop();
		if( u.x == end_r && u.y == end_c ) { print( u ); return; }
		for( int i = 0 ; i < 3 ; i++ ){
			Node v = walk( u , i );
			if( has_edge[u.x][u.y][u.dir][i] && inside(v.x,v.y) && d[v.x][v.y][v.dir] < 0 ){
				p[v.x][v.y][v.dir] = u;
				d[v.x][v.y][v.dir] = d[u.x][u.y][u.dir] + 1;
				q.push(v);
			}
		}	
	}
	cout << name << endl;
	cout << "  No Solution Possible" << endl;

}	

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("x.txt","r",stdin);
	while( cin >> name ){
		memset(has_edge,0,sizeof(has_edge));
		if( name == "END" ){
			break;
		}
		cin >> start_r >> start_c >> start_dir >> end_r >> end_c;
		s_x = start_r ; s_y = start_c;
		if( start_dir[0] == 'N' ) start_r--;
		else if( start_dir[0] == 'S' ) start_r++;
		else if( start_dir[0] == 'E' ) start_c++;
		else start_c --;
		start.x = start_r; start.y = start_c ; start.dir = dir_id(start_dir[0]); 
		s_dir = dir_id(start_dir[0]);
		int x , y ;
		while( cin >> x ){
			if( x == 0 ) break;
			cin >> y ;
			string s;
			while( cin >> s ){
				if( s[0] == '*' ) break;
				int len = s.size();
				int id = dir_id(s[0]);
				for( int i = 1; i < len ; i++ ){
					has_edge[x][y][id][turns_id(s[i])] = 1;
				}
			}
		}
		BFS();
	}
	return 0;
}