404 Not Found ← 問題文
パソコン甲子園2010の双子のソースを改変したレベルの解法。ソースが溜まっていくとこういうことが出来るから良い。
確定ノード情報のために五次元配列を確保したけど、初めて使ったよ5次元配列とか・・・。
#include <iostream> #include <vector> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int dx[] = { 0, 0,-1, 1, 0}; int dy[] = { 1,-1, 0, 0, 0}; class NODE{ public: int x1; int y1; int x2; int y2; int depth; }; int conv(char c){ switch(c){ case '2':return 0; case '4':return 2; case '8':return 1; case '6':return 3; case '5':return 4; } } int main(){ int X,Y,tx,ty,kx,ky; char data[22][22]; string cmd; while(cin >> Y >> X , X){ rep(i,22)rep(j,22)data[i][j] = '+'; rep(i,Y)rep(j,X){ cin >> data[1+i][1+j]; if(data[1+i][1+j] == 'A'){ tx = 1+j; ty = 1+i; data[1+i][1+j] = '.'; } if(data[1+i][1+j] == 'B'){ kx = 1+j; ky = 1+i; data[1+i][1+j] = '.'; } } cin >> cmd; queue<NODE> Q; NODE t = {tx,ty,kx,ky,0}; Q.push(t); bool done[22][22][22][22][10] = {0}; while(Q.size()){ NODE q = Q.front();Q.pop(); if( done[q.x1][q.y1][q.x2][q.y2][q.depth%cmd.size()] )continue; done[q.x1][q.y1][q.x2][q.y2][q.depth%cmd.size()] = true; if(q.x1 == q.x2 && q.y1 == q.y2){ cout << q.depth << " " << q.y1-1 << " " << q.x1-1 << endl; goto end; } rep(i,5){ NODE next; next.x1 = q.x1 + dx[i]; next.y1 = q.y1 + dy[i]; next.x2 = q.x2 + dx[ conv( cmd[q.depth%cmd.size()] ) ]; next.y2 = q.y2 + dy[ conv( cmd[q.depth%cmd.size()] ) ]; next.depth = q.depth + 1; if(data[next.y1][next.x1] != '.'){ next.x1 = q.x1; next.y1 = q.y1; } if(data[next.y2][next.x2] == '+'){ next.x2 = q.x2; next.y2 = q.y2; } Q.push(next); } } cout << "impossible" << endl; end:; } }