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

AOJ1041~1050 - (2012/03/31 (土) 15:56:07) のソース

----
*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()){
	}
 }