「AtCoder Code-Festival-2017-qualA-D」Four Coloring

Description

给定一个 $h \times w$ 的网格，试给其中所有格子染 RYGB 四种颜色之一，使得网格上任意一对曼哈顿距离为 $d$ 的格子颜色不同。

$(2 \leq h,w \leq 500, 1\leq d \leq h + w - 2)$

Source

[Luogu]AT3557

[AtCoder]Code-Festival-2017-qualA-D

Solution

曼哈顿距离并不方便处理，我们考虑把它转化为切比雪夫距离。（详见 常用距离算法详解）

举个例子，当 $d = 3$ 时，我们把曼哈顿坐标系（网格）旋转 $45^\circ$（即 $(i,j) \Rightarrow (i+j,i - j)$ ），得到切比雪夫坐标系。

其中蓝点是到红点距离为 $3$ 的点，切比雪夫坐标系中的点到周围 $8$ 个点的距离都是 $1$ 。

考虑把切比雪夫坐标系分成多个网格，每个网格的大小是 $d \times d$ 。如果我们给同一网格中的点染相同的颜色（中心网格的所有点对的切比雪夫距离都 $< d$），那么对于任意一个网格，它周围 $8$ 个网格的颜色都应该与它不同，因为周围网格存在到中心网格距离为 $d$ 的点。

怎么给网格染色呢？

我们会发现对于任意一个网格，它左上，右上，左下，右下网格的横坐标与纵坐标的奇偶性是相同的，上下网格的奇偶性也是相同的，左右网格的奇偶性也是相同的，但周围 $8$ 个网格都与中心网格的奇偶性不同。

所以一种有效的方式是按网格横坐标，纵坐标的奇偶性分成 $4$ 种颜色。对于坐标 $(x,y)$，其所在的网格为 $(\left \lfloor \frac{x}{d} \right \rfloor,\left \lfloor \frac{y}{d} \right \rfloor)$ 。若设奇数为 $1$，偶数为 $0$，则 $4$ 种颜色分别对应 $(0,0),(0,1),(1,0),(1,1)$ 。时间复杂度为 $O(hw)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int h, w, d;
char s[4] = { 'R', 'Y', 'G', 'B' };//四种颜色 

int main() {
    read(h), read(w), read(d);
    for (int i = 1; i <= h; ++i, putchar('\n'))
        for (int j = 1; j <= w; ++j) {
            int x = i + j + w, y = i - j + w;
            //转成切比雪夫坐标系，+w 是因为防止坐标出现负数，方便得出奇偶性 
            putchar(s[((x / d) & 1) * 2 + ((y / d) & 1)]);
        }
    return 0;
}