プログラマ専用SNS ミクプラ

コード:

#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
void search();
std::string changeColor(std::string worm,int p);


std::string s1;

std::set<std::string> worms;//一度通った色を覚える
std::set<std::string> nows;//ｎターン目の虫の色たち
std::set<std::string> nexts;//次の虫の色たち
std::set<std::string>::iterator it;

char cWorm[11];
int minTime;
int n;
int timeMax=1000000000;

int main(){
	
	scanf("%s",cWorm);
	n=strlen(cWorm);
	while(cWorm[0]!='0' && n>1){
		minTime=0;
		worms.clear();
		nows.clear();
		nexts.clear();
		search();
		if(minTime==timeMax){
			printf("NA\n");
		}else{
			printf("%d\n",minTime);
		}
		scanf("%s",cWorm);
		n=strlen(cWorm);
	}
}


int rgbCount(std::string cWorm){
	int colorCount=0;//同色のカウント
	char t=cWorm[0];
	for(int i=0;i<n;i++){
		if(t==cWorm[i]) colorCount++;
		else break;
	}
	return colorCount;
}


void search(){
	//幅優先探索で検索する。
	//3＾10≒60000なので何とかなる
	nows.insert(cWorm);
	worms.insert(cWorm);

	if(rgbCount(std::string(cWorm))==n){minTime=0; return;}
	std::string worm,nextWorm;
	
	int changeCount;
	while(changeCount>0){
		minTime++;
		changeCount=0;
		it=nows.begin();
		nexts.clear();
		while(it!=nows.end()){
			worm=(*it);
			for(int i=0;i<n-1;i++){
				if(worm[i]!=worm[i+1]){
					nextWorm=changeColor(worm,i);
					if(worms.find(nextWorm)==worms.end()){
						worms.insert(nextWorm);
						nexts.insert(nextWorm);
						changeCount++;
						if(rgbCount(nextWorm)==n) return;
					}
				}
			}
			it++;
		}
		nows.clear();
		it=nexts.begin();
		while(it!=nexts.end()){
			nows.insert(*it);
			it++;
		}
	}
	minTime=timeMax;
	return ;
}

std::string changeColor(std::string worm,int p){
	char t1,t2,t3;
	std::string nextworm=worm;
	t1=worm[p];
	t2=worm[p+1];
	if((t1=='r' && t2=='g') || (t1=='g' && t2=='r')){
		nextworm[p]=nextworm[p+1]='b';
	}else if((t1=='r' && t2=='b') || (t1=='b' && t2=='r')){
		nextworm[p]=nextworm[p+1]='g';
	}else if((t1=='g' && t2=='b') || (t1=='b' && t2=='g')){
		nextworm[p]=nextworm[p+1]='r';
	}
	return nextworm;
}