AOJ 0179 - Mysterious Worm

赤青緑の3色あって，
文字列の隣り合う2色が違うとき，そのどちらの色でもない色に変化しうる。
そのとき与えられた文字列が1色になるまでにかかる最短時間は?

・アイデア
問題文に貼り付けられた図を見てうわっむずそうって最近まで思ってた
でもこれはstring型のmapに最短手をぶちこんで幅優先探索すれば余裕なのではって気づく。
なんのひねりもない幅優先探索の問題に落とせた

・実装

#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;

bool isSameColor(string a){
	char b=a[0];
	int s=a.size();
	
	for(int i=0; i<s; ++i){
		if(a[i]!=b) return false;
	}
	
	return true;	
}

int main(){
	string s;
	while(cin>>s){
		if(s=="0") break;
		
		queue<string> que;
		map<string, long> mp;
		
		que.push(s);
		mp[s]=0;	
		
		bool found=false;
		while(!que.empty()){
			string v=que.front();
			que.pop();
			
			int size=v.size();
			for(int i=0; i<size-1; ++i){
				string tmp=v;
				
				if((tmp[i]=='r'&&tmp[i+1]=='g') || (tmp[i]=='g'&&tmp[i+1]=='r')) tmp[i]=tmp[i+1]='b';
				else if((tmp[i]=='r'&&tmp[i+1]=='b') || (tmp[i]=='b'&&tmp[i+1]=='r')) tmp[i]=tmp[i+1]='g';
				else if((tmp[i]=='b'&&tmp[i+1]=='g') || (tmp[i]=='g'&&tmp[i+1]=='b')) tmp[i]=tmp[i+1]='r';
				
				if(mp.find(tmp) == mp.end()){
					que.push(tmp);
					mp[tmp]=mp[v]+1;	
				}
				
				if(isSameColor(tmp)){
					cout << mp[tmp] << endl;	
					found=true;
					break;
				}	
			}	
			
			if(found) break;
		}
		
		if(!found) printf("NA\n");
		
	}
}

途中に愚直すぎる書き方をしてとても見苦しい部分があるが，あれはなんとかなるのだろうか。笑

裏紙

ほぼ競プロ、たまに日記

AOJ 0179 - Mysterious Worm