「AOJ71～80」の編集履歴（バックアップ）一覧に戻る

AOJ71～80 - (2011/08/13 (土) 17:48:26) の編集履歴(バックアップ)

---

0071　Bombs Chain

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

<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

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

<stdio.h>

<queue>

<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);
}

}