【题意】给定h,w,d，要求构造矩阵h*w满足任意两个曼哈顿距离为d的点都不同色，染四色。
【算法】结论+矩阵变换
【题解】
曼哈顿距离是一个立着的正方形，不方便处理。d=|xi-xj|+|yi-yj|
将矩阵旋转45°，转为切比雪夫距离（正方形）。d=max{|xi-xj|,|yi-yj|}
（图片来自Atcoder editorial）
定义旋转后的每个点坐标为(x-y,x+y)。（实际处理中x-y+10000避免负数）
将新坐标按d划分区域，就可以发现每个点必须和八连通的块异色，如下图。
（图片来自Atcoder editorial）
八连通染四色的方法：color(x%2+y%2*2)，本质上是00,01,10,11四色，这样八连通自然就不同了（如上图），为了0~3就用0+0,0+2,1+0,1+2来表示。
另外，此题在d为奇数时有结论，直接按副对角线染色（假设当前颜色1，走d步后达到的一定是2或4）
#include<cstdio> int h,w,d; char s[]="RGBY"; int main(){ scanf("%d%d%d",&h,&w,&d); if(d&1){ for(int i=0;i<h;++i){ for(int j=0;j<w;++j)putchar(s[i+j&1]); putchar(10); } }else{ for(int i=0;i<h;++i){ for(int j=0;j<w;++j){ int x=i+j,y=i-j+10000; putchar(s[(x/d&1)+(y/d&1)*2]); } putchar(10); } } return 0; }