Official

B - Grid Repainting 4 Editorial by evima


Table of contents

  1. Intended solution
  2. Implementation
  3. Sample Codes


1. Intended solution

The method below constructs a coloring that satisfies the requirements. Here, we paint the squares in the order starting at the top-left square, but it is not mandatory.

  • If \((1, 1)\) is not painted yet, paint it in a color different from those of all adjacent squares. [1]
  • If \((1, 2)\) is not painted yet, paint it in a color different from those of all adjacent squares.
  • If \((1, 3)\) is not painted yet, paint it in a color different from those of all adjacent squares.
  • \(:\)
  • If \((H, W)\) is not painted yet, paint it in a color different from those of all adjacent squares.

The figure below shows this method applied to a specific grid.

[1] Here, the existence of such a color is guaranteed, because there are at most four adjacent squares, while there are five colors available.



2. Implementation

As in the (C++) code below, the solution can be implemented using nested loops. The two-dimensional array d[i][j] represents the color of \((i, j)\), where d[i][j]=0 means it is unpainted yet, and the other values mean it is painted in Color d[i][j].

As a side note, in problems involving grids, it can be helpful to have arrays that store information indicating the positions of adjacent squares, such as:

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

For codes in Python, JAVA, C, see 3. Sample Codes.

#include <iostream>
using namespace std;

// Positions of adjancent squares
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

// Input/Output, the grid
int H, W;
int d[709][709];

int main() {
	// Step #1. Input
	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; } // Not painted
			if (c == '1') { d[i][j] = 1; } // Color 1
			if (c == '2') { d[i][j] = 2; } // Color 2
			if (c == '3') { d[i][j] = 3; } // Color 3
			if (c == '4') { d[i][j] = 4; } // Color 4
			if (c == '5') { d[i][j] = 5; } // Color 5
		}
	}

	// Step #2. Simulation
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (d[i][j] != 0) {
				// already painted, no need to paint it
				continue;
			}

			// used[k] = true when there is an adjacent square in Color 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;
			}

			// Look for the color to use
			// In this program, choose the usable color with the smallest ID
			for (int k = 1; k <= 5; k++) {
				if (used[k] == true) continue;
				d[i][j] = k;
				break;
			}
		}
	}

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


3. Sample Codes

posted:
last update: