AOJの0179、Mysterious Wormをc++で解きました。
「典型的な横型探索」と言われていたのですが、
まぁ〜面白いほどにc++に馴染めなくて（mapが書き方が分からなくて）ハマりました。
一度見た虫の色を管理するclosedをどう書けばよいか悩みました。
わざわざmap使わなくても済む方法があったら教えて下さい…。
実装部分のみだと1時間弱くらいだと思います。 mapと戯れている間を含めると2時間弱でした。
問題文はこちら
| #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; | |
| } |