## B - Grid Repainting 4 Editorial by evima

### Table of contents

- Intended solution
- Implementation
- 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: