【Atcoder】CODE FESTIVAL 2017 qual A D

【题意】给定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&){

        for(int i=;i<h;++i){

            for(int j=;j<w;++j)putchar(s[i+j&]);

            putchar();

        }

    }else{

        for(int i=;i<h;++i){

            for(int j=;j<w;++j){

                int x=i+j,y=i-j+;

                putchar(s[(x/d&)+(y/d&)*]);

            }

            putchar();

        }

    }

    return ;

}

巴特西

【Atcoder】CODE FESTIVAL 2017 qual A D - Four Coloring

最新文章

热门文章