読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 643, Division 2, Level 1 : TheKingsArmyDiv2

問題概要

 R \times C のグリッド状に兵士が配置されている.各兵士の精神状態は,「幸せ」または「つらみ」のいずれかの状態をとる.
 「幸せ」な兵士が 2 人以上隣接しているとき,その兵士達は楽しくおしゃべりをするので,回りにも幸せな状態が伝播する.正確には,おしゃべりをしている兵士に 4 近傍で隣接している兵士は,単位時間経過後に「幸せ」な状態になる.
 各兵士の精神状態を表す文字列配列 state が与えられる.state を構成する各文字列は 2 種類の文字 'H', 'S' からなり,それぞれ「幸せ」,「つらみ」に対応する.state_{ ij } が 'H' のとき,i 行目 j 列目の初期の精神状態が「幸せ」であることを表し,そうでないとき(= 'S' のとき)「つらみ」であることを表す.
 王様は,全ての兵士に「幸せ」になって欲しいと考えている.そのために,兵士を一人選んで(何らかの方法で)「幸せ」な状態にする操作を任意回行える.兵士全員が「幸せ」になるまでにかかる時間には特に制限が無いとき,必要な操作の最小回数を求めよ.

解法

 まず題意より,「幸せ」の伝播によって「幸せ」になった兵士がいるとすると,その兵士は「幸せ」の伝播元の兵士と隣接していることが分かります.すると次の時刻には,その兵士から更に隣接する兵士に「幸せ」が伝播します.つまり,演繹的に考えると,1 回でも「幸せ」の伝播が起これば,「幸せ」は盤面全体に伝播するため,王様はそれ以上手を下す必要はありません.従って,state に一箇所以上隣接する 'H' が存在するようにすればよい,ということになります.
 さて,隣接するセルに操作をすることで,高々 2 つの 'S' を 'H' に変更すれば隣接する 'H' を作れるため,解も高々 2 になります.すると判定は,

  • 最初から隣接する 'H' がある → 何もしなくてよい
  • 'H' が存在しない → 隣接するセルを 1 組選んでその 2 箇所を 'H' に変える
  • それ以外(孤立した 'H' が存在する) → いずれかの 'H' に隣接するセルを 1 つ選んで 'H' に変える

という簡単な場合分けになります.
 このことを判定するために,state 中の '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;
	}
};