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: