Official

B - Grid Repainting 4 Editorial by E869120

解説の目次

この解説は以下の 4 つのセクションから構成されます。

  1. 想定解法
  2. 想定解法の実装
  3. 解法を思いつくためのヒント
  4. サンプルコード

すぐに解答を知りたい方は、「1. 想定解法」 をご覧ください。


1. 想定解法

以下のような方法により、条件を満たす答えを 1 つ構成することができます。なお、ここでは説明の都合上、左上のマスから順番に塗っていきますが、必ずしもそうする必要はありません。

  • マス \((1, 1)\) にまだ色が塗られていなければ、どの隣接するマスとも異なる色で塗る [注 1]
  • マス \((1, 2)\) にまだ色が塗られていなければ、どの隣接するマスとも異なる色で塗る
  • マス \((1, 3)\) にまだ色が塗られていなければ、どの隣接するマスとも異なる色で塗る
  • \(:\)
  • マス \((H, W)\) にまだ色が塗られていなければ、どの隣接するマスとも異なる色で塗る

具体的なマス目に対して上の塗り方を適用すると、下図のようになります。

[注 1] ここで、どの隣接するマスとも異なる色が必ず存在することが保証されます。なぜなら、隣接するマスの数（高々 4 つ）より色の選択肢の数（5 つ）の方が多いからです。


2. 想定解法の実装

以下のように、多重ループを使うことで実装できます。二次元配列 d[i][j] はマス \((i, j)\) の色を示しており、d[i][j]=0 のときまだ塗られていないこと、そうでないとき色 d[i][j] で塗られていることを意味します。

なお、マス目を管理する問題では、隣接するマスの情報を管理する配列を用意しておくと、実装が楽になることがあります。

  • int dx[4] = {1, 0, -1, 0};
  • int dy[4] = {0, 1, 0, -1};

Python・JAVA・C のソースコードは、「3. サンプルコード」をご覧ください。

#include <iostream>
using namespace std;

// 隣接するマスの情報
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

// 入出力、マス目の情報
int H, W;
int d[709][709];

int main() {
	// Step #1. 入力
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char c; cin >> c;
			if (c == '.') { d[i][j] = 0; } // 塗られていない場合
			if (c == '1') { d[i][j] = 1; } // 色 1 の場合
			if (c == '2') { d[i][j] = 2; } // 色 2 の場合
			if (c == '3') { d[i][j] = 3; } // 色 3 の場合
			if (c == '4') { d[i][j] = 4; } // 色 4 の場合
			if (c == '5') { d[i][j] = 5; } // 色 5 の場合
		}
	}

	// Step #2. シミュレーション
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (d[i][j] != 0) {
				// すでに塗られている場合、新たに塗る必要はない
				continue;
			}

			// 変数 used[k] は色 k が隣接マスに存在するかを表す
			bool used[6] = { false, false, false, false, false, false };
			for (int k = 0; k < 4; k++) {
				int sx = i + dx[k];
				int sy = j + dy[k];
				used[d[sx][sy]] = true;
			}

			// どの色で塗れるかを探す
			// このプログラムは、どの隣接するマスとも異なる色のうち番号が最小の色で塗っている
			for (int k = 1; k <= 5; k++) {
				if (used[k] == true) continue;
				d[i][j] = k;
				break;
			}
		}
	}

	// Step #3. 出力
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cout << d[i][j];
		}
		cout << endl;
	}
	return 0;
}


3. 解法を思いつくためのヒント

この問題では、どのような順序で色を塗っても正しい解答を出すことができるため、それといった「解法を思いつくためのヒント」はありません。しかし、「全探索や動的計画法などのアルゴリズムを使う必要があるのではないか」と難しく考えすぎて、自然な発想に至らないのは、競技プログラミングではよくあることです。

解法が分からないときは、まずは自然な発想や単純な解法から考えることが大切です。


4. サンプルコード

posted:
last update: