rockdu
Problem Statement
We have a grid with H rows and W columns of squares. We will represent the square at the i-th row from the top and j-th column from the left as (i, j). Also, we will define the distance between the squares (i1, j1) and (i2, j2) as |i1−i2|+|j1−j2|.
Snuke is painting each square in red, yellow, green or blue. Here, for a given positive integer d, he wants to satisfy the following condition:
- No two squares with distance exactly d have the same color.
Find a way to paint the squares satisfying the condition. It can be shown that a solution always exists.
Constraints
- 2≤H,W≤500
- 1≤d≤H+W−2
Input
Input is given from Standard Input in the following format:
H W d
Output
Print a way to paint the squares satisfying the condition, in the following format. If the square (i, j) is painted in red, yellow, green or blue, cij should be R, Y, G or B, respectively.
c11c12…c1W : cH1cH2…cHW
Sample Input 1
2 2 1
Sample Output 1
RY GR
There are four pairs of squares with distance exactly 1. As shown below, no two such squares have the same color.
- (1, 1), (1, 2) :
R,Y - (1, 2), (2, 2) :
Y,R - (2, 2), (2, 1) :
R,G - (2, 1), (1, 1) :
G,R
Sample Input 2
2 3 2
Sample Output 2
RYB RGB
There are six pairs of squares with distance exactly 2. As shown below, no two such squares have the same color.
- (1, 1) , (1, 3) :
R,B - (1, 3) , (2, 2) :
B,G - (2, 2) , (1, 1) :
G,R - (2, 1) , (2, 3) :
R,B - (2, 3) , (1, 2) :
B,Y - (1, 2) , (2, 1) :
Y,R
做完这道题才明白了切比雪夫距离和曼哈顿距离的转换有什么用。
在曼哈顿距离下，和一个点距离为k的点排成的是一个菱形。在离散的矩阵中很难操作。
但是如果转换成切比雪夫距离，那么这些店就构成一个大的矩形！
这样我们再进行操作就轻松多了~
切比雪夫距离简单说来就是国际象棋上的王从一个格子走到另一个格子的步数。也就是两点横纵坐标差中更大的那个。详见：切比雪夫距离
考虑到这道题，我们转换为切比雪夫距离后，只需要对一些横纵划分出的块染色，我们只需要知道当前格子在哪个块中就好了。
#include<cstdio>
using namespace std;
int n, m, k, x, y, _2k;
char col[] = "RGBY";
char mp[505][505];
int main() {
scanf("%d%d%d", &n, &m, &k), _2k = k * 2;
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j) {
x = n + i + j, y = m + i - j;
mp[i][j] = col[2 * ((x / k) & 1) + ((y / k) & 1)];
}
for(register int i = 1; i <= n; ++i) {
for(register int j = 1; j <= m; ++j)
putchar(mp[i][j]);
putchar('\n');
}
return 0;
}
没有帐号? 立即注册