2017-Karakuri Doll

Karakuri Doll | Aizu Online Judge

解法

行きのグラフと帰りのグラフを作ってDFS．
速度を確保するためにハッシュマップとハッシュセットを使っているが，実際には二分探索木で十分間に合う．

実装(C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <set>
#include <map>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <boost/tuple/tuple_io.hpp>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
#include <boost/functional/hash.hpp>
using namespace std;
int W,H;
char MAP[64][16];
#define REP(i,x)for(int i=0;i<(int)x;i++)
int sx,sy,sd,tx,ty,td;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int get_direction(int x,int y){
	REP(k,4){
		if(MAP[x+dx[k]][y+dy[k]]=='.')return k;
	}
}
typedef boost::tuple<int,int,int,int,int,int> P;
typedef boost::tuple<int,int,int> State;
using boost::hash_combine;
struct State_hash{
	size_t operator()(const State &a)const{
		size_t seed=0;
		hash_combine(seed,(size_t)a.get<0>());
		hash_combine(seed,(size_t)a.get<1>());
		hash_combine(seed,(size_t)a.get<2>());
		return seed;
	}
};
struct P_hash{
	size_t operator()(const P &a)const{
		size_t seed=0;
		hash_combine(seed,a.get<0>());
		hash_combine(seed,a.get<1>());
		hash_combine(seed,a.get<2>());
		hash_combine(seed,a.get<3>());
		hash_combine(seed,a.get<4>());
		hash_combine(seed,a.get<5>());
		return seed;
	}
};
tr1::unordered_set<P,P_hash> ac;
tr1::unordered_set<State,State_hash> ac2;
tr1::unordered_map<State,vector<State>,State_hash > node;
int ans=0;
void solve1(int x,int y,int d){
	P state(x,y,d,0,0,0);
	if(ac.find(state)!=ac.end())return;
	ac.insert(state);
	while(MAP[x+dx[d]][y+dy[d]]!='#'){
		x+=dx[d];
		y+=dy[d];
	}
	if(x==tx&&y==ty){
		ans=1;
		return;
	}
	solve1(x,y,(d+1)%4);solve1(x,y,(d+3)%4);
}
void solve2(int x,int y,int d){
	State state(x,y,d);
	if(ac2.find(state)!=ac2.end())return;
	ac2.insert(state);
	while(MAP[x+dx[d]][y+dy[d]]!='#'){
		x+=dx[d];y+=dy[d];
	}
	node[State(x,y,d)].push_back(state);
	solve2(x,y,(d+1)%4);solve2(x,y,(d+3)%4);
}
void solve3(int x1,int y1,int d1,int x2,int y2,int d2){
	P state(x1,y1,d1,x2,y2,d2);
	if(ans==2)return;
	if(ac.find(state)!=ac.end())return;
	ac.insert(state);
	while(MAP[x1+dx[d1]][y1+dy[d1]]!='#'){
		x1+=dx[d1];y1+=dy[d1];
	}
	State st(x2,y2,d2);
	vector<State> &Node=node[st];
	REP(i,Node.size()){
		State &next=Node[i];
		if(x1==tx&&y1==ty&&next==State(tx,ty,td)){
			ans=2;
			return;
		}
		for(int j=-1;j<=1;j+=2){
			solve3(x1,y1,(d1+j+4)%4,next.get<0>(),next.get<1>(),(next.get<2>()+j+4)%4);
			if(ans==2){
				return;
			}
		}
	}
}
string res[3]={
		"He cannot bring tea to his master.",
		"He cannot return to the kitchen.",
		"He can accomplish his mission."
};
int main() {
	while(cin>>W>>H,W){
		REP(i,H){
			string in;
			cin>>in;
			REP(j,W){
				MAP[j][i]=in[j];
				if(MAP[j][i]=='K'){
					MAP[j][i]='.';
					sx=j,sy=i;
				}
				if(MAP[j][i]=='M'){
					tx=j,ty=i;
				}
			}
		}
		ans=0;
		ac.clear();
		td=get_direction(tx,ty);sd=get_direction(sx,sy);
		solve1(sx,sy,get_direction(sx,sy));
		if(ans>=1){
			ac2.clear();
			node.clear();
			solve2(tx,ty,td);
			REP(i,4){
				solve3(sx,sy,get_direction(sx,sy),sx,sy,i);
			}
		}
		cout<<res[ans]<<endl;
	}
}