AOJ 1281: The Morning after Halloween

タイトルがタイトルなので11/1の午前中に解いておこうと思い、解いた。

解法：実装するだけ。650とは思えない。空白マスがあんまり多くないことが大事。

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char str[20][20];
int dx[]={1,0,-1,0,0};
int dy[]={0,1,0,-1,0};
int num[20][20];
int bfs[130][130][130];
int to[130][5];
int cnt;
struct wolf{
	int a,b,c;
	wolf(int A,int B,int C){
		a=A;b=B;c=C;
	}
	wolf(){
		a=b=c=cnt;
	}
};
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&b,&a,&c),a){
		gets(str[0]);
		for(int i=0;i<a;i++)gets(str[i]);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)num[i][j]=-1;
		int cnt=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++)if(str[i][j]!='#')num[i][j]=cnt++;
		}
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)if(str[i][j]!='#'){
			for(int k=0;k<5;k++){
				if(0<=i+dx[k]&&i+dx[k]<a&&0<=j+dy[k]&&j+dy[k]<b&&str[i+dx[k]][j+dy[k]]!='#'){
					to[num[i][j]][k]=num[i+dx[k]][j+dy[k]];
				}else to[num[i][j]][k]=-1;
			}
		}
		queue<wolf>Q;
		wolf S;
		wolf T;
		for(int i=0;i<a;i++)for(int j=0;j<b;j++){
			if(str[i][j]=='a'){S.a=num[i][j];str[i][j]='.';}
			if(str[i][j]=='b'){S.b=num[i][j];str[i][j]='.';}
			if(str[i][j]=='c'){S.c=num[i][j];str[i][j]='.';}
			if(str[i][j]=='A'){T.a=num[i][j];str[i][j]='.';}
			if(str[i][j]=='B'){T.b=num[i][j];str[i][j]='.';}
			if(str[i][j]=='C'){T.c=num[i][j];str[i][j]='.';}
		}
		for(int i=0;i<=cnt;i++)for(int j=0;j<=cnt;j++)for(int k=0;k<=cnt;k++)
			bfs[i][j][k]=-1;
		Q.push(S);
		bfs[S.a][S.b][S.c]=0;
		while(Q.size()&&!~bfs[T.a][T.b][T.c]){
			wolf at=Q.front();Q.pop();
			for(int i=0;i<5;i++){
				if(!~to[at.a][i])continue;
				if(c==1){
					if(!~bfs[to[at.a][i]][at.b][at.c]){
						bfs[to[at.a][i]][at.b][at.c]=bfs[at.a][at.b][at.c]+1;
						Q.push(wolf(to[at.a][i],at.b,at.c));
					}
					continue;
				}
				for(int j=0;j<5;j++){
					if(!~to[at.b][j])continue;
					if(c==2){
						int ta=to[at.a][i];
						int tb=to[at.b][j];
						if(!~bfs[ta][tb][at.c]&&ta!=tb&&(ta!=at.b||tb!=at.a)){
							bfs[ta][tb][at.c]=bfs[at.a][at.b][at.c]+1;
							Q.push(wolf(ta,tb,at.c));
						}
						continue;
					}
					for(int k=0;k<5;k++){
						if(!~to[at.c][k])continue;
						int ta=to[at.a][i];
						int tb=to[at.b][j];
						int tc=to[at.c][k];
						if(!~bfs[ta][tb][tc]&&ta!=tb&&ta!=tc&&tb!=tc&&(ta!=at.b||tb!=at.a)&&
						(tb!=at.c||tc!=at.b)&&(tc!=at.a||ta!=at.c)){
							bfs[ta][tb][tc]=bfs[at.a][at.b][at.c]+1;
							Q.push(wolf(ta,tb,tc));
						}
					}
				}
			}
		}
		printf("%d\n",bfs[T.a][T.b][T.c]);
	}
}