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; }