AOJ 2017 Karakuri Doll

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017）

制約条件

H≦16
W≦50
部屋の最も外側のマスは壁である。

方針

まずは、スタートからゴールへ行けるかだけを探索する。
これは、普通にロボットの動きをシミュレートする幅優先探索をすればいい。

次に、ゴールへ行きつつ、逆実行するとゴールからスタートへ戻れるプログラムがあるかを探索する。
これは、スタートからゴールへ順実行で行く経路と、
ゴールからスタートへ戻る経路を逆から、すなわちスタートから後ろ向きにゴールへ行く経路を同時に探索すればいい。

帰りの探索では、壁のほうを向けるマスが、次にキューに入れるマスである。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w, sy, sx, sd, gd;
string in[16];

bool solve(){
	static bool v[16][64][4];
	memset(v, 0, sizeof(v));
	queue<pi> q;
	q.push(mp(sy * w + sx, sd));
	v[sy][sx][sd] = 1;
	while(!q.empty()){
		int y = q.front().first / w, x = q.front().first % w;
		int dir = q.front().second; q.pop();
		
		while(in[y+dy[dir]][x+dx[dir]] !='#') y += dy[dir], x += dx[dir];
		if(in[y][x] == 'M') return 1;
		dir = dir + 1 & 3;
		rep(d, 2){
			if(!v[y][x][dir]){
				v[y][x][dir] = 1;
				q.push(mp(y * w + x, dir));
			}
			dir = dir + 2 & 3;
		}
	}
	return 0;
}
bool solve2(){
	set<pair<pi, pi> > s;
	queue<pair<pi, pi> > q;
	rep(d, 4){
		q.push(mp(mp(sy * w + sx, sd), mp(sy * w + sx, d)));
		s.insert(mp(mp(sy * w + sx, sd), mp(sy * w + sx, d)));
	}
	while(!q.empty()){
		int y1, x1, d1, y2, x2, d2;
		y1 = q.front().first.first / w, x1 = q.front().first.first % w;
		y2 = q.front().second.first / w, x2 = q.front().second.first % w;
		d1 = q.front().first.second, d2 = q.front().second.second;
		q.pop();
		
		while(in[y1 + dy[d1]][x1 + dx[d1]] != '#') y1 += dy[d1], x1 += dx[d1];
		while(1){
			for(int i = 1; i < 5; i += 2){
				int nd1 = d1 + i & 3, nd2 = d2 + i & 3;
				if(in[y2 + dy[nd2]][x2 + dx[nd2]] == '#'){
					if(!s.count(mp(mp(y1 * w + x1, nd1), mp(y2 * w + x2, nd2)))){
						s.insert(mp(mp(y1 * w + x1, nd1), mp(y2 * w + x2, nd2)));
						q.push(mp(mp(y1 * w + x1, nd1), mp(y2 * w + x2, nd2)));
					}
				}
			}
			if(in[y2 - dy[d2]][x2 - dx[d2]] == '#') break;
			y2 -= dy[d2], x2 -= dx[d2];
		}
		if(in[y1][x1] == 'M' && in[y2][x2] == 'M' && d2 == gd) return 1;
	}
	return 0;
}

int main()
{
	while(cin >> w >> h, w){
		rep(i, h) cin >> in[i];
		rep(i, h) rep(j, w){
			if(in[i][j] == 'K'){
				sy = i, sx = j;
				rep(d, 4){
					int ny = i + dy[d], nx = j + dx[d];
					if(in[ny][nx] != '#') sd = d;
				}
			}
			if(in[i][j] == 'M'){
				rep(d, 4){
					int ny = i + dy[d], nx = j + dx[d];
					if(in[ny][nx] != '#') gd = d;
				}
			}
		}
		bool iki = solve(), kaeri = solve2();
		if(iki && kaeri) puts("He can accomplish his mission.");
		else if(iki) puts("He cannot return to the kitchen.");
		else puts("He cannot bring tea to his master.");
	}
	
	return 0;
}