スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




ふしぎな虫

2008.09.15 13:10  パソコン甲子園 2008

問題 パソコン甲子園2008 07

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


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

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


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

pck200807_2.gif
出典:パソコン甲子園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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。