AOJ 0179 Mysterious Worm Time Limit : 5 sec, Memory Limit : 65536 KB

AOJ_0179.cpp

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef pair<string, int> bug;
typedef map<string, int> closeMap;

// １色になっていればOK
int isOK(string str) {
    for ( int i = 0; i < str.size(); i++ ) {
        if ( str[0] != str[i] ) return 0;
    }
    return 1;
}

// aでもbでもない色を返す
char cc(char a, char b) {
    // 並び替え
    if ( b < a ) {
        char tmp = a;
        a = b;
        b = tmp;
    }

    if ( a == 'b' && b == 'g' ) {
        return 'r';
    } else if ( a == 'b' && b == 'r' ) {
        return 'g';
    } else {
        return 'b';
    }
}

void wfs(string str) {
    int cnt = -1;
    string first = str;
    queue<bug> open;
    closeMap close;

    // 初期状態をプッシュ
    open.push( make_pair(str, 0) );

    // ２度同じデータが入らないようcloseする
    close.insert( closeMap::value_type(str, 1) );

    while(!open.empty()) {
        bug b = open.front(); open.pop();
        string cs = b.first;

        if ( isOK(cs) ) {
            cnt = b.second;
            break;
        }

        int c = 0;
        for ( int i = 1; i < cs.size(); i++ ) {
            // 色が異なっていたら
            if ( cs[i-1] != cs[i] ) {
                string tmp = cs;

                // 変化する色を取得
                char nc = cc(cs[i-1], cs[i]);
                tmp[i-1] = nc;
                tmp[i] = nc;

                // 既にあるならopenに入れない
                if ( close[tmp] ) continue;
                open.push( make_pair(tmp, b.second+1) );
                close[tmp] = 1;
                c++;
            }
        }
    }

    if ( cnt == -1 ) {
        cout << "NA" << endl;
    } else {
        cout << cnt << endl;
    }


}

int main() {
    string n;

    while ( cin >> n, n != "0" ) {
        wfs(n);
    }

    return 0;
}