問題概要
のグリッド状に兵士が配置されている．各兵士の精神状態は，「幸せ」または「つらみ」のいずれかの状態をとる．
「幸せ」な兵士が 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; } };
