题解 AT3557 【Four Coloring】

## Description 给定一个 $h \times w$ 的网格，试给其中所有格子染 `RYGB` 四种颜色之一，使得网格上任意一对曼哈顿距离为 $d$ 的格子颜色不同。 $(2 \leq h,w \leq 500, 1\leq d \leq h + w - 2)$ ## Solution 曼哈顿距离并不方便处理，我们考虑把它转化为切比雪夫距离。（详见 **[常用距离算法详解](https://www.luogu.org/blog/xuxing/Distance-Algorithm)**） 举个例子，当 $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 ```cpp #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; } ```