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

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

AOJ再挑戦71~75 - (2014/02/02 (日) 15:50:53) の1つ前との変更点

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

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

 *問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);
   	}
  }  
 
 
 
-*問72
+*問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);
      }
  }