ふしぎな虫

問題 パソコン甲子園2008 07

いくつかの玉のような形をした体節でつながっている不思議な虫がいます。体節は赤(r)、緑(g)、青(b)のいづれかの色をもっています。この虫が、以下の条件のもとで１秒ごとに体節の色を変えます：

• 色が変わるのは、隣合っている色違いの２つの体節のペア 1 組のみ。


• そのようなペアは、2 つの体節の色のどちらでもない色に同時に変わる。

この虫の色の変化を、2 秒後まですべて表したものが以下の図です。


出典：パソコン甲子園２００８

与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい（不可能な場合は NA と出力して下さい）。

入力例
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0

出力例
5
7
1
6
NA
8
0
4

解説

状態空間における幅優先探索で解きます。
ここでは、状態を r, g, b からなる文字列(そのまま)で表します。
状態を保存するためにハッシュ法を用いるのが良いでしょうが、
STL の map を使うと実装が楽になります（速度は落ちるでしょう）。

サンプルプログラム

001 #include<iostream>
002 #include<queue>
003 #include<map>
004 using namespace std;
005 #define INFTY (1<<21)
006 
007 bool isSameColor( string state ){
008     for ( int i = 1; i < state.size(); i++ ){
009         if ( state[i-1] != state[i] ) return false;
010     }
011     return true;
012 }
013 
014 char getColor( char c1, char c2 ){
015     if ( c1 == 'g' ) return (c2=='r' ? 'b' : 'r');
016     else if ( c1 == 'b' ) return (c2=='r' ? 'g' : 'r');
017     else if ( c1 == 'r' ) return (c2=='b' ? 'g' : 'b');
018 }
019 
020 int bfs(string s){
021     queue<string> Q;
022     map<string, bool> V;
023     map<string, int> D;
024     
025     Q.push(s);
026     V[s] = true;
027     D[s] = 0;
028     string u, v;
029     
030     while(!Q.empty()){
031         u = Q.front(); Q.pop();
032         if ( isSameColor(u) ) return D[u];
033         for ( int i = 1; i < u.size(); i++ ){
034             if ( u[i-1] != u[i] ){
035                 v = u;
036                 v[i-1] = v[i] = getColor(u[i-1], u[i]);
037                 if ( !V[v] ){
038                     V[v] = true;
039                     D[v] = D[u] + 1;
040                     Q.push(v);
041                 }
042             }
043         }
044     }
045     
046     return INFTY;
047 }
048 
049 int main(){
050     string initial;
051     while( cin >> initial ){
052         if ( initial == "0" ) break;
053         int cost = bfs( initial );
054         if ( cost == INFTY ) cout << "NA" << endl;
055         else cout << cost << endl;
056     }
057     return 0;
058 }