2137-Time Trial

問題概要

図が全て!

解法

BFS
状態量は50^4なので普通に間に合う

実装(C++)

#include <iostream>
#include <queue>
#include <tr1/unordered_set>
#include <tr1/unordered_map>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
char MAP[16][16];
int toval[16][16];
int W,H;
#define REP(i,x) for(int i=0;i<(int)x;i++)
int gx[3],gy[3];
struct State{
	short x[3],y[3];
	short hx,hy;
	short turn;
};

State init;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
short minturn[55][55][55][55];
#define MINTURN(state)minturn[toval[state.hx][state.hy]][toval[state.x[0]][state.y[0]]][toval[state.x[1]][state.y[1]]][toval[state.x[2]][state.y[2]]]
int solve(){
	memset(minturn,0x3F,sizeof(minturn));
	queue<State> que;
	que.push(init);
	MINTURN(init)=0;
	while(!que.empty()){
		State now=que.front();que.pop();
		//終了判定
		int exit=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(now.x[i]==gx[j]&&now.y[i]==gy[j]){
					exit++;break;
				}
			}
		}
		if(exit==3)return now.turn;
		REP(k,4){
			int nx=now.hx+dx[k];
			int ny=now.hy+dy[k];
			if(MAP[nx][ny]=='#')continue;//壁には入れない
			State next=now;
			next.hx=nx;next.hy=ny;
			next.turn++;
			bool ok=true;
			REP(i,3){
				if(next.x[i]==nx&&next.y[i]==ny){
					next.x[i]+=dx[k];
					next.y[i]+=dy[k];
					//衝突チェック
					if(MAP[next.x[i]][next.y[i]]=='#'){
						ok=false;
						break;
					}
					REP(j,3){
						if(i==j)continue;
						if(next.x[i]==next.x[j]&&next.y[i]==next.y[j]){
							ok=false;
							break;
						}
					}
					break;
				}
			}
			if(ok){
				if(MINTURN(next)>next.turn){
					MINTURN(next)=next.turn;
					que.push(next);
				}
			}
		}
	}
	return -1;
}
int main() {
	while(cin>>W>>H){
		if(W==0)break;
		int c=0,c2=0;
		REP(i,H){
			string in;
			cin>>in;
			REP(j,W){
				MAP[j][i]=in[j];
				if(MAP[j][i]=='*'){
					init.x[c]=j;
					init.y[c++]=i;
				}
				if(MAP[j][i]=='_'){
					gx[c2]=j;
					gy[c2++]=i;
				}
				if(MAP[j][i]=='@'){
					init.hx=j;init.hy=i;
				}
			}
		}
		c=0;
		REP(y,H)REP(x,W){
			if(MAP[x][y]!='#'){
				toval[x][y]=c++;
			}
		}
		cout<<solve()<<endl;
	}
	return 0;
}