「AOJ再挑戦71~75」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦71~75 - (2014/02/02 (日) 15:50:53) のソース

*問71 Bombs Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0071
ボン○ーマンもどきの爆発連鎖を扱った問題。
解法
再帰以外思いつかなかった。


 #include<stdio.h>
 #include<string.h>
 
 int dx[4]={1,0,-1,0};
 int dy[4]={0,1,0,-1};
 
 bool inArea(int x,int y){
 	return (0<=x) && (x<8) && (0<=y) && (y<8);
 }
 
 void chain(char map[8][9],int x,int y){
 	map[y][x]='0';
 	for(int i=0;i<4;i++){
 		for(int j=1;j<=3;j++){
 			int nx=x+dx[i]*j;
 			int ny=y+dy[i]*j;
 			if(inArea(nx,ny)&&map[ny][nx]=='1'){
  				chain(map,nx,ny);
 			}
 		}
  	}
 } 
  
 void calc(int turn){
  	char map[8][9];
 	for(int i=0;i<8;i++){
 		scanf("%s",map[i]);
 	}
  	int sx,sy;
  	scanf("%d %d",&sx,&sy);
 	sx--;
 	sy--;
 	chain(map,sx,sy);
  	printf("Data %d:\n",turn);
 	for(int i=0;i<8;i++){
 		printf("%s\n",map[i]);
 	}
 } 
  
 int main(){
 	int n;
 	scanf("%d",&n);
  	for(int i=1;i<=n;i++){
 		calc(i);
  	}
 }  



*問72Carden Lantern
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0072
街路にランタンを設置する数を最小にする問題。
解法
最小全域木をプリム法で求めるだけです。 
 
 #include<stdio.h>
 #include<vector>
 #include<queue>
 #include<string.h>
 
 struct S{
    int to,cost;
    bool operator<(const S& s)const{
        return cost>s.cost;
    }
 };
 
 void calc(int n){
    int m,a,b,len;
    std::vector<S> G[101];
    std::priority_queue<S> pq;
    S s,s1;
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d,%d,%d",&a,&b,&len);
        s.cost=len/100-1;
        s.to=b;
        G[a].push_back(s);
        if(a==0)pq.push(s);
        s.to=a;
        G[b].push_back(s);
        if(b==0)pq.push(s);
    }
    bool spents[101];
    memset(spents,false,sizeof(spents));
    spents[0]=true;
    int count=1,ans=0;
    while(pq.empty()==false){
        s=pq.top();
        pq.pop();
        if(spents[s.to]==true)continue;
        spents[s.to]=true;
        count++;
        ans+=s.cost;
        if(count==n)break;
        for(int i=0;i<G[s.to].size();i++){
            s1=G[s.to][i];
            if(spents[s1.to]==true)continue;
            pq.push(s1);
        }
    }
     printf("%d\n",ans);
 }
 
  
 int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        calc(n);
     }
 }