※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

AOJ1041~1050 - (2012/03/31 (土) 15:56:07) の1つ前との変更点

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

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

 ----
 *1045 Split Up!
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045
 戦闘力が与えられるので戦闘力の合計が均等になるように2チームにわける問題。
-普通に解くだけなら簡単な問題で簡単に解いたけど、高速化することを考えたら突然難問に変化する。
+普通に解くだけなら全探索にちょっと枝刈で簡単に解いたけど、高速化することを考えたら突然難問に変化する。
 どうやって速度を稼げばいいのかな?
 
 
 
  #include<stdio.h>
  #include<set>
  int sum,herf,n,datas[21],t,ans;
  void saiki(int deep,int now){
 	if(herf<now)return;
 	t=sum-now*2;
 	ans=ans>t?t:ans;
 	if(deep!=n){
 		saiki(deep+1,now+datas[deep]);
 		saiki(deep+1,now);
 	}
  }
  int main(){
 	while(scanf("%d",&n)){
 		if(n==0)break;
 		sum=0;
 		ans=2000000000;
 		for(int i=0;i<n;i++){
 			scanf("%d",&datas[i]);
 			sum+=datas[i];
 		}
 		herf=sum/2;
 		saiki(0,0);
 		printf("%d\n",ans);
 	}
  }
 
 
 
 
 
 
 
 ----
 *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()){
 	}
  }