「AOJ1300～1310」の編集履歴（バックアップ）一覧に戻る
AOJ1300～1310 - (2013/03/27 (水) 05:02:08) のソース
*1304
英語が苦手な人には厳しい問題。
ｎ*ｎマスのマップが与えられる。
＃がウイルス、.がウイルスの発生してないマス、@がウイルス除去車を表す。
ターン制でセルオートマトンで繁殖するウイルスがあり、それを除去するための除去車がマス目を移動する。
最小の移動手数でウイルスを削除するときのターン数を答えよ。
ルール
ルールＡ 除去車はターン初めに移動すること、今いるマスにとどまることはできない、隣接８方向に移動できウイルスのいないマスにしか移動できない。
ルールＢ 移動後除去車のいるマスは保護機能によりウイルスは侵入できないが、他のセルを計算するときは除去車はウイルスとして扱う
ルールＣ ウイルスは、周囲8マス中３マスがウイルスならばそのマスで新たに発生する。
ルールＤ ウイルスがいきているマスの周囲２マスにウイルスがいるならウイルスはそのマスに生存し続ける。
ルールＤ ウイルスはそれ以外の条件では死滅し'.'マスに戻る。
ルールＢが曲者ですね。
これを読解できないとこの問題は解けません。
解法
マス目が最大２５マスなので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とｎは空データ
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
グループ名:それに所属している人の個人名か下位となるグループ名のリストがｎ行にわたって与えられる。
一行目のグループに所属している人の数を答えよという問題。
解法
再帰探索で全探索して同じグループは２度調べないとすればあっという間に答えが出ます。
#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);
}
}
