読者です 読者をやめる 読者になる 読者になる

AOJ Problem 1046 : Ghost Buster!

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