問題概要
のグリッド状に兵士が配置されている.各兵士の精神状態は,「幸せ」または「つらみ」のいずれかの状態をとる.
「幸せ」な兵士が 2 人以上隣接しているとき,その兵士達は楽しくおしゃべりをするので,回りにも幸せな状態が伝播する.正確には,おしゃべりをしている兵士に 4 近傍で隣接している兵士は,単位時間経過後に「幸せ」な状態になる.
各兵士の精神状態を表す文字列配列 が与えられる. を構成する各文字列は 2 種類の文字 'H', 'S' からなり,それぞれ「幸せ」,「つらみ」に対応する. が 'H' のとき, 行目 列目の初期の精神状態が「幸せ」であることを表し,そうでないとき(= 'S' のとき)「つらみ」であることを表す.
王様は,全ての兵士に「幸せ」になって欲しいと考えている.そのために,兵士を一人選んで(何らかの方法で)「幸せ」な状態にする操作を任意回行える.兵士全員が「幸せ」になるまでにかかる時間には特に制限が無いとき,必要な操作の最小回数を求めよ.
解法
まず題意より,「幸せ」の伝播によって「幸せ」になった兵士がいるとすると,その兵士は「幸せ」の伝播元の兵士と隣接していることが分かります.すると次の時刻には,その兵士から更に隣接する兵士に「幸せ」が伝播します.つまり,演繹的に考えると,1 回でも「幸せ」の伝播が起これば,「幸せ」は盤面全体に伝播するため,王様はそれ以上手を下す必要はありません.従って, に一箇所以上隣接する 'H' が存在するようにすればよい,ということになります.
さて,隣接するセルに操作をすることで,高々 2 つの 'S' を 'H' に変更すれば隣接する 'H' を作れるため,解も高々 2 になります.すると判定は,
- 最初から隣接する 'H' がある → 何もしなくてよい
- 'H' が存在しない → 隣接するセルを 1 組選んでその 2 箇所を 'H' に変える
- それ以外(孤立した 'H' が存在する) → いずれかの 'H' に隣接するセルを 1 つ選んで 'H' に変える
という簡単な場合分けになります.
このことを判定するために, 中の 'H' の数と,隣接するものの有無を知る必要があります.これは簡単なループと条件分岐によって計算できます.
コード
#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) class TheKingsArmyDiv2 { public: int getNumber( vector <string> state ) { const int H = state.size(), W = state[0].size(); int cnt = 0; bool adj = false; REP( i, 0, H ) { REP( j, 0, W ) { if ( state[i][j] == 'S' ) { continue; } ++cnt; adj += i + 1 < H && state[ i + 1 ][j] == 'H'; adj += j + 1 < W && state[i][ j + 1 ] == 'H'; } } return cnt == 0 ? 2 : 1 - adj; } };