Contest Duration: - (local time) (120 minutes) Back to Home
Official

## B - Grid Repainting 4 Editorial by evima

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;

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;
}


posted:
last update: