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

1304

英語が苦手な人には厳しい問題。
n*nマスのマップが与えられる。
#がウイルス、.がウイルスの発生してないマス、@がウイルス除去車を表す。
ターン制でセルオートマトンで繁殖するウイルスがあり、それを除去するための除去車がマス目を移動する。
最小の移動手数でウイルスを削除するときのターン数を答えよ。

ルール
ルールA 除去車はターン初めに移動すること、今いるマスにとどまることはできない、隣接8方向に移動できウイルスのいないマスにしか移動できない。
ルールB 移動後除去車のいるマスは保護機能によりウイルスは侵入できないが、他のセルを計算するときは除去車はウイルスとして扱う
ルールC ウイルスは、周囲8マス中3マスがウイルスならばそのマスで新たに発生する。
ルールD ウイルスがいきているマスの周囲2マスにウイルスがいるならウイルスはそのマスに生存し続ける。
ルールD ウイルスはそれ以外の条件では死滅し'.'マスに戻る。
ルールBが曲者ですね。
これを読解できないとこの問題は解けません。

解法
マス目が最大25マスなのでint型でマップの状態を表し車の位置とセットでstd::setに放り込んで幅優先探索して十分間に合いました。
行列演算やビット演算を賢く使って計算量を低減する方法はあるらしいのですが詳しくないので次の状態の計算は一マスずつ素朴に計算してます。
一行単位で一気に計算する方法もありそうなのでこれから勉強しようかと思います。


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

struct State{
	int umap;
	int x,y;
	int turn;
	bool operator<(const State& s)const{
		if(umap!=s.umap)return umap<s.umap;
 		if(x!=s.x)return x<s.x;
		return y<s.y;
	}
};
int mask[]={0,1,3,7,15,31};
int bitToCount[]={0,1,1,2,1,2,2,3};

void print(State s,int n){
	printf("\n");
	printf("(%d %d)\n",s.x,s.y);
	int num=s.umap;
	for(int i=0;i<n;i++){
 		for(int j=0;j<n;j++){
			int p2=i*n+j;
			printf("%c",((num>>p2)&1)==0?'.':'#');
		}
		printf("\n");
	}
 	int a;
	scanf("%d",&a);
}

bool nextCalc(State& s,int n){
	int p=s.y*n+s.x;//pは感染しない
	int rs[7]={0},next=0,add=s.umap;
 	if(((s.umap>>p)&1)==1)return false;//感染エリアに移動したので不可
//0とnは空データ
 		add|=(1<<p);
		for(int i=0;i<n;i++){
			rs[i+1]=((add>>(n*i))&mask[n]);//1行ずつ取り出す、行列を使う方法は?
		}
		int p2;
		for(int i=1;i<=n;i++){
			for(int j=0;j<n;j++){
				int bitCount;
				int slide=j-1;
				if(j==0){
 					bitCount =bitToCount[(rs[i-1])&3];
					bitCount    +=bitToCount[(rs[i-0])&2];
					bitCount    +=bitToCount[(rs[i+1])&3];
				}else{
					bitCount =bitToCount[(rs[i-1]>>slide)&7];
					bitCount    +=bitToCount[(rs[i-0]>>slide)&5];
					bitCount    +=bitToCount[(rs[i+1]>>slide)&7];
				}
				p2=(i-1)*n+j;
				int f=(add>>p2)&1;
				if(p2==p)continue;
 				if(bitCount==3||bitCount==3-f){
					next|=(1<<p2);
				}
			}
 		}
		s.umap=next;
	return true;
}

void calc(int n){
	std::set<State> memo;
	std::queue<State> qu;
	char row[10];
	State s1,nextS;
	s1.umap=0;
	for(int i=0;i<n;i++){
		scanf("%s",row);
 		int r=0;
		for(int j=0;j<n;j++){
			if(row[j]=='@'){
				s1.x=j;
				s1.y=i;
				s1.turn=0;
			}else if(row[j]=='#'){
				r|=(1<<j);
 			}
		}
		s1.umap|=(r<<(n*i));
	}
	qu.push(s1);
	int dxs[]={1,1,0,-1,-1,-1, 0, 1};
	int dys[]={0,1,1, 1, 0,-1,-1,-1};
	while(qu.empty()==false){
		nextS=s1=qu.front();
		qu.pop();
		if(s1.umap==0)break;
		if(memo.find(s1)!=memo.end())continue;
		memo.insert(s1);
		nextS.turn++;
 		for(int i=0;i<8;i++){
		nextS.x=s1.x+dxs[i];
 			nextS.y=s1.y+dys[i];
			nextS.umap=s1.umap;
			if(nextS.x<0||n<=nextS.x||nextS.y<0||n<=nextS.y)continue;
			if(nextCalc(nextS,n)==true){
 				//print(nextS,n);
				qu.push(nextS);
			}
 		}
	}
	if(s1.umap==0){
 		printf("%d\n",s1.turn);
	}else{
		printf("-1\n");
	}
}

int main(){
	int n;
	while(1){
 		scanf("%d",&n);
	if(n==0)break;
		calc(n);
	}
	
}





1305 Membership Management

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1305
グループ名:それに所属している人の個人名か下位となるグループ名のリストがn行にわたって与えられる。
一行目のグループに所属している人の数を答えよという問題。

解法
再帰探索で全探索して同じグループは2度調べないとすればあっという間に答えが出ます。


#include<stdio.h>
#include<map>
#include<set>
#include<string>

std::map<std::string,std::set<std::string> > groups;
std::set<std::string> memo;

std::set<std::string> saiki(std::string name){
	std::set<std::string> re,t1;
	if(memo.find(name)!=memo.end())return re;
	for(std::set<std::string>::iterator it=groups[name].begin();it!=groups[name].end();it++){
		if(groups.find((*it))!=groups.end()){
			t1=saiki((*it));
			re.insert(t1.begin(),t1.end());
 		}else{
		re.insert((*it));
 		}
	}
	memo.insert(name);
	return re;
} 

void Deployment(int n){
	
	std::set<std::string> s1;
	std::string str,str2,startName;
	char gName[30],name[30],c;
 	groups.clear();
	memo.clear();
	
	for(int i=0;i<n;i++){
		scanf("%[^:]%c",gName,&c);
		str=gName;
		if(i==0)startName=str;
		groups[str]=s1;
 		while(1){
			scanf("%[^.,]%c",name,&c);
			str2=name;
			groups[str].insert(str2);
			if(c=='.')break;
		}
		scanf("%c",&c);
 	}
	printf("%d\n",saiki(startName).size());
	
}

int main(){
	int n;
 	char c;
	while(1){
		scanf("%d%c",&n,&c);
		if(n==0)break;
		Deployment(n);
	}
}