AOJ 0179 Mysterious Worm

初めて記事を書くことになります。
これからいろんな問題を解いて、その感想やらを書き綴りながらアルゴリズムをマスターしていきたいところ。

• • • • • • • • • • • • • • • • • • • • • • -

AOJ 0179 Mysterious Worm

id:kyuridenamida さんの

http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144

こちらから幅優先探索の問題を解いてみた。

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

typedef pair<string, int> P;

int bfs(string worm){
	queue<P> que;
	que.push(P(worm, 0));

	map<string, int> d;
	
	while(!que.empty()){
		P p = que.front();
		que.pop();

		//重複パターンはcontinue
		if(d[p.first]) continue;

		string str = p.first;

		//全色同じかどうかのチェック
		bool flag = false;
		for(int i=0;i<str.size()-1;i++){
			if(str[i] != str[i+1]){
				flag = true;
				break;
			}
		}
		//同じならreturn
		if(!flag) return p.second;

		//重複パターン判別用
		d[p.first] = p.second;

		for(int i=0;i<str.size()-1;i++){
			//隣り合わせで色が異なるとき
			if(str[i] != str[i+1]){
				char temp;
				string next;

				//tempに含まれない一色を代入
				if(str[i] != 'b' && str[i+1] != 'b'){
					temp = 'b';
				}else if(str[i] != 'g' && str[i+1] != 'g'){
					temp = 'g';
				}else{
					temp = 'r';
				}

				//変化後の順番をnextに詰め込む
				next = str;
				next[i] = next[i+1] = temp;

				//キューにプッシュ
				que.push(P(next, p.second+1));
			}
		}
	}
	return -1;
}

int main(){
	string worm;
	while(cin >> worm && worm != "0"){
		int ret = bfs(worm);
		if(ret>=0) cout << ret << endl;
		else cout << "NA" << endl;
	}
}

mapに対して[]演算子で存在しないものを参照すると自動で生成されるということを初めて知りました。

あとは、今まで殆ど使ってなかったtypedefに慣れるいい機会になった。かな。