「AOJ1041~1050」の編集履歴(バックアップ)一覧に戻る

AOJ1041~1050 - (2012/01/02 (月) 09:35:52) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+----
+*1046 Ghost Buster!
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1046
+升目で区切られたマップ上を一定のルールで移動する幽霊を最短時間で捕まえる問題。
+あるマスで捕まえるとき、そのマスまで最短時間で移動しそのマスに幽霊が来るのを待てばいい。
+この簡単なことに気づくのにやたらと時間のかかった問題。
+考え方さえ分かれば後は場合分けが少しめんどくさいだけの実装ゲーム。
 
+
+ #include<stdio.h>
+ #include<string.h>
+ //               0 1 2 3  4 5 6 7  8
+ const int dxs[]={0,0,0,0,-1,0,1,0, 0};
+ const int dys[]={0,0,1,0, 0,0,0,0,-1};
+ const int max=100000000;
+ char map[21][21];
+ bool gMoveMemo[21][21];
+ int moveMemo[21][21];
+ int h,w;
+ bool areaOut(int x,int y){
+	if(x<0||x>=w||y<0||y>=h) return true;
+	return false;
+ }
+ void saiki(int x,int y,int deep){
+	if(areaOut(x,y)||map[y][x]=='#'||moveMemo[y][x]<=deep) return;
+	moveMemo[y][x]=deep;
+	saiki(x+1,y,deep+1);
+	saiki(x-1,y,deep+1);
+	saiki(x,y+1,deep+1);
+	saiki(x,y-1,deep+1);
+ }
+ void print(){
+	for(int y=0;y<h;y++){
+		for(int x=0;x<w;x++){
+			printf("%2d",moveMemo[y][x]==max?-1:moveMemo[y][x]);
+		}
+		printf("\n");
+	}
+ }
+ bool setData(){
+	scanf("%d %d",&h,&w);
+	if(h+w==0)return false;	
+	int sx,sy,gx,gy;
+	memset(gMoveMemo,true,sizeof(gMoveMemo));
+	for(int y=0;y<h;y++){
+		scanf("%s",&map[y]);
+		for(int x=0;x<w;x++){
+			moveMemo[y][x]=max;
+			if(map[y][x]=='A'){
+				sx=x;
+				sy=y;
+			}else if(map[y][x]=='B'){
+				gx=x;
+				gy=y;
+			}
+		}
+	}
+	saiki(sx,sy,0);
+	//print();
+	char com[12];
+	scanf("%s",com);
+	int size=strlen(com),count=1,nx,ny,ans=max,ansX,ansY,turn=0;
+	while(count!=0&&ans>turn){
+		count=0;
+		for(int p=0;p<size;p++){
+			nx=dxs[com[p]-'0']+gx;
+			ny=dys[com[p]-'0']+gy;
+			turn++;
+			if(areaOut(nx,ny)==false){
+				gx=nx;
+				gy=ny;
+			}
+			if(moveMemo[gy][gx]<=turn){
+				gMoveMemo[gy][gx]=false;
+				count++;
+				if(ans>turn){
+					ans=turn;
+					ansX=gx;
+					ansY=gy;
+				}
+			}else if(gMoveMemo[gy][gx]==true){
+				count++;
+				gMoveMemo[gy][gx]=false;
+			}else if(moveMemo[gy][gx]!=max){
+				count++;
+			}
+		}
+	}
+	if(ans==max)printf("impossible\n");
+	else printf("%d %d %d\n",ans,ansY,ansX);
+	return true;
+ }
+ int main(){
+	while(setData()){
+	}
+ }