ふしぎな虫
2008.09.15 13:10 パソコン甲子園 2008
問題 パソコン甲子園2008 07
いくつかの玉のような形をした体節でつながっている不思議な虫がいます。体節は赤(r)、緑(g)、青(b)のいづれかの色をもっています。この虫が、以下の条件のもとで1秒ごとに体節の色を変えます:
この虫の色の変化を、2 秒後まですべて表したものが以下の図です。

出典:パソコン甲子園2008
与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい(不可能な場合は NA と出力して下さい)。
入力例
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0
出力例
5
7
1
6
NA
8
0
4
いくつかの玉のような形をした体節でつながっている不思議な虫がいます。体節は赤(r)、緑(g)、青(b)のいづれかの色をもっています。この虫が、以下の条件のもとで1秒ごとに体節の色を変えます:
- 色が変わるのは、隣合っている色違いの2つの体節のペア 1 組のみ。
- そのようなペアは、2 つの体節の色のどちらでもない色に同時に変わる。
この虫の色の変化を、2 秒後まですべて表したものが以下の図です。

出典:パソコン甲子園2008
与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい(不可能な場合は 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |