「AOJ71～80」の編集履歴（バックアップ）一覧はこちら

AOJ71～80 - (2011/08/13 (土) 17:48:26) の１つ前との変更点

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

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

*0071　Bombs Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
探索で愚直に実装。
これも丁寧に書くだけの問題。



#include<stdio.h>
char map[9][9];

void saiki(int x,int y){
	int nx,ny;
	for(int i=-3;i<4;i++){
		nx=x+i;
		ny=y;
		if(8>nx && nx>-1 && map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
		nx=x;
		ny=y+i;
		if(ny>7 || ny<0) continue;
		if(map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
	}
}

void setMap(int no){
	for(int i=0;i<8;i++){
		scanf("%s",map[i]);
	}
	int sx,sy;
	scanf("%d %d",&sx,&sy);
	saiki(sx-1,sy-1);
	printf("Data %d:\n",no+1);

	for(int i=0;i<8;i++){
		printf("%s\n",map[i]);
	}
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap(i);
	}
}

*0071　Bombs Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
探索で愚直に実装。
これも丁寧に書くだけの問題。



#include<stdio.h>
char map[9][9];

void saiki(int x,int y){
	int nx,ny;
	for(int i=-3;i<4;i++){
		nx=x+i;
		ny=y;
		if(8>nx && nx>-1 && map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
		nx=x;
		ny=y+i;
		if(ny>7 || ny<0) continue;
		if(map[ny][nx]=='1'){
			map[ny][nx]='0';
			saiki(nx,ny);
		}
	}
}

void setMap(int no){
	for(int i=0;i<8;i++){
		scanf("%s",map[i]);
	}
	int sx,sy;
	scanf("%d %d",&sx,&sy);
	saiki(sx-1,sy-1);
	printf("Data %d:\n",no+1);

	for(int i=0;i<8;i++){
		printf("%s\n",map[i]);
	}
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap(i);
	}
}






----
*0072
典型的なプリム法の問題。
最初に解いた時はプリム法を知らず、プリム法と同じ方法を自力で思いついたて実装したので初めての時はコードが上手くいくかドキドキものだった問題。
結局上手くいったのでよかった。
最初のコードの高速化を目指して少しコードを弄ってる。

#include<stdio.h>
#include<queue>
#include<vector>

struct load{
	int p1,p2,len;
	bool operator<(const load l)const{
		return len>l.len;
	}
};

void setMap(int n,int m){
	int points[101]={0};
	std::priority_queue<load> loads;
	std::vector<load> map[101];
	std::vector<load>::iterator it,end;
	load l,start;
	start.len=2000000000;
	for(int i=0;i<m;i++){
		scanf("%d,%d,%d",&l.p1,&l.p2,&l.len);
		l.len=l.len/100-1;
		map[l.p1].push_back(l);
		map[l.p2].push_back(l);
		start=l.len<start.len?l:start;
	}
	int count=1,ans=0,addOK;
	loads.push(start);
	
	while(n>count && loads.empty()==false){
		l=loads.top();
		loads.pop();
		addOK=false;
		if(points[l.p1]==0){
			addOK=true;
			points[l.p1]=1;
			it=map[l.p1].begin();
			end=map[l.p1].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(points[l.p2]==0){
			addOK=true;
			points[l.p2]=1;
			it=map[l.p2].begin();
			end=map[l.p2].end();
			while(it!=end){
				loads.push(*it);
				it++;
			}
		}
		if(addOK==true){
			count++;
			ans+=l.len;
		}
	}
	printf("%d\n",ans);
}

int main(){
	int n,m;
	scanf("%d",&n);
	while(n!=0){
		scanf("%d",&m);
		setMap(n,m);
		scanf("%d",&n);
	}
}