Algorithm

aoj0179.cpp

#include <bits/stdc++.h>

using namespace std;

typedef pair<string, int> P;

//すべての色が同じかを判定
bool judge(string str) {
	for (int i = 0; i < str.size(); ++i) {
		if (str[0] != str[i]) return false;
	}
	return true;
}

//隣り合う2色のどちらでもない色を返す
char color(char a, char b){
	if((a == 'g' && b == 'r') || (a == 'r' && b == 'g'))return 'b';
	else if((a == 'b' && b == 'r') || (a == 'r' && b == 'b')) return 'g';
	else if((a == 'g' && b == 'b') || (a == 'b' && b == 'g')) return 'r';
}

int solve(string s ){

	queue<P> q;
	map<string, int> m;
	q.push(P(s, 0));	//キューに初期状態を入れる

	while (!q.empty()) {	//キューが空の状態になるまで
		P p = q.front();
		q.pop();
		if(m[p.first]) continue;	//重複を避ける
		string now = p.first;
		if (judge(now)) return p.second;
		m[p.first] = p.second;
		for (int i = 0; i < now.size() - 1; ++i) {
			if (now[i] != now[i+1]){	//隣り合う2色が異なるとき
				char tmp = color(now[i], now[i + 1]);
				string D = now;
				D[i] = tmp;
				D[i + 1] = tmp;
				q.push(P(D, p.second + 1));
			}
		}
	}
	return -1;
}

int main() {
	string worm;
	while (cin >> worm) {
		if (worm == "0") break;
		int count = solve(worm);
		if (count == -1) cout << "NA" << endl;
		else cout << count << endl;
	}
	return 0;
}