PKU 2644-Maze

問題概要

NxNの迷路が与えられる．プレイヤーは障害物のあるマスに入ることが出来ない．
また，プレイヤーには目隠しがされどこのマスに要るかは知ることが出来ないが，方角を知ることは出来る．
プレイヤーがどのマスに居ても迷路から脱出出来るような移動方法のうち一番短いものを答えよ．
ただし，迷路からの脱出とは，端のマスに辿りつくことを言う．

解法

最良優先探索.
人が居る全てのマスのうち最も脱出に時間がかかるものの時間をpとすると，pが小さい順に探索していく．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
int MAP[8][8];
int dist[8][8];
typedef pair<int,int> P;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
string direction[4]={"east","south","west","north"};
int n;
inline int p2i(int x,int y,int w=n){
	return x+y*w;
}
struct State{
	int priority;
	long long state;
	State(int p,long long s):priority(p),state(s){}
};
bool operator<(const State &a,const State &b){
	return a.priority>b.priority;
}
void BFS(int x,int y){
	queue<P> que;
	map<P,int> ac;
	ac[P(x,y)]=0;
	que.push(P(x,y));
	while(!que.empty()){
		P t=que.front();que.pop();
		int now=ac[t];
		if(t.first==0||t.first==n-1||t.second==0||t.second==n-1){
			dist[x][y]=now;
			break;
		}
		REP(i,4){
			int nx=t.first+dx[i],ny=t.second+dy[i];
			if(MAP[nx][ny]==0){
				if(ac.find(P(nx,ny))==ac.end()){
					ac[P(nx,ny)]=now+1;
					que.push(P(nx,ny));
				}
			}
		}
	}
}

priority_queue<State> que;
void add_queue(long long s){
	int md=0;
	for(int x=0;x<n-2;x++){
		for(int y=0;y<n-2;y++){
			if((s>>p2i(x,y,n-2))&1){
				md=max(md,dist[x+1][y+1]);
			}
		}
	}
	que.push(State(md,s));
}
map<lli,int> turn; //最短ターン
map<lli,lli> back; //前回の行動
int ans=999;
void solve(lli s){
	turn[s]=0;
	add_queue(s);
	while(!que.empty()){
		State s=que.top();que.pop();
		int now=turn[s.state];
		if(s.state==0){
			ans=now;
		}
		if(now+s.priority>=ans)continue;
		//移動先
		int nx,ny;
		REP(k,4){
			lli next=0;
			REP(x,n-2)REP(y,n-2){
				if((s.state>>(p2i(x,y,n-2)))&1){
					nx=x+1+dx[k],ny=y+1+dy[k];
					if(MAP[nx][ny]==1)nx=x+1,ny=y+1;
					if(nx>0&&nx<n-1&&ny>0&&ny<n-1){
						next|=1LL<<p2i(nx-1,ny-1,n-2);
					}
				}
			}
			if(turn.find(next)==turn.end()||turn[next]>now+1){
				turn[next]=now+1;
				back[next]=s.state;
				add_queue(next);
			}
		}
	}
}
int diff(lli a,lli b){
	int nx,ny;
	REP(k,4){
		lli next=0;
		REP(x,n-2)REP(y,n-2){
			if((a>>(p2i(x,y,n-2)))&1){
				nx=x+1+dx[k],ny=y+1+dy[k];
				if(MAP[nx][ny]==1)nx=x+1,ny=y+1;
				if(nx>0&&nx<n-1&&ny>0&&ny<n-1){
					next|=1LL<<p2i(nx-1,ny-1,n-2);
				}
			}
		}
		if(next==b)return k;
	}
	return -1;
}
long long start=0;
void show_ans(lli now){
	if(now==start)return;
	lli next=back[now];
	show_ans(next);
	cout<<direction[diff(next,now)]<<endl;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		string in;
		cin>>in;
		for(int j=0;j<n;j++){
			MAP[j][i]=in[j]=='O';
		}
	}
	REP(x,n)REP(y,n){
		if(MAP[x][y]==0)BFS(x,y);
	}


	for(int i=0;i<n-2;i++){
		for(int j=0;j<n-2;j++){
			if(MAP[i+1][j+1]==0){
				start|=1LL<<p2i(i,j,n-2);
			}
		}
	}
	if(start==0)return 0;

	solve(start);

	show_ans(0);

	return 0;
}