AT3557 Four Coloring

    • 22通过
    • 28提交
  • 题目来源 AtCoder 3557
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

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

    输入格式

    一行两个正整数$H ,W , d$

    $1 \leq H,W \leq 500 , 1 \leq d \leq H + W - 2$

    输出格式

    输出一个$H \times W$的字符矩阵表示染色方案

    题目描述

    縦 $ H $ 行、横 $ W $ 列のマス目があります。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と表します。 また、マス $ (i_1,\ j_1) $ と $ (i_2,\ j_2) $ の間の距離を $ |i_1\ -\ i_2|\ +\ |j_1\ -\ j_2| $ と定義します。

    すぬけ君は各マスを 赤 / 黄 / 緑 / 青 のいずれかの色で塗ろうとしています。 このとき、正の整数 $ d $ に対して、次の条件が成り立つようにします。

    • 距離がちょうど $ d $ であるようなマスのペアには、異なる色が塗られている。

    条件を満たす色の塗り方をひとつ求めてください。 解は必ず存在することが示せます。

    输入输出格式

    输入格式:

    Input is given from Standard Input in the following format:

     $ H $   $ W $   $ d $ 

    输出格式:

    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, $ c_{ij} $ should be R, Y, G or B, respectively.

     $ c_{11} $  $ c_{12} $  $ ... $  $ c_{1W} $ 
     $ : $ 
     $ c_{H1} $  $ c_{H2} $  $ ... $  $ c_{HW} $ 

    输入输出样例

    输入样例#1: 复制
    2 2 1
    输出样例#1: 复制
    RY
    GR
    输入样例#2: 复制
    2 3 2
    输出样例#2: 复制
    RYB
    RGB
    输入样例#3: 复制
    2 2 1
    输出样例#3: 复制
    RY
    GR
    输入样例#4: 复制
    2 3 2
    输出样例#4: 复制
    RYB
    RGB

    说明

    制約

    • $ 2\ \leq\ H,\ W\ \leq\ 500 $
    • $ 1\ \leq\ d\ \leq\ H\ +\ W\ -\ 2 $

    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 $ (i_1,\ j_1) $ and $ (i_2,\ j_2) $ as $ |i_1\ -\ i_2|\ +\ |j_1\ -\ j_2| $ .

    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\ \leq\ H,\ W\ \leq\ 500 $
    • $ 1\ \leq\ d\ \leq\ H\ +\ W\ -\ 2 $

    Sample Explanation 1

    距離がちょうど $ 1 $ であるようなマスのペアは、次の $ 4 $ 組です。 右側に示したように、どのペアにも異なる色が塗られています。

    • $ (1,\ 1) $ と $ (1,\ 2) $ : RY
    • $ (1,\ 2) $ と $ (2,\ 2) $ : YR
    • $ (2,\ 2) $ と $ (2,\ 1) $ : RG
    • $ (2,\ 1) $ と $ (1,\ 1) $ : GR

    Sample Explanation 2

    距離がちょうど $ 2 $ であるようなマスのペアは、次の $ 6 $ 組です。 右側に示したように、どのペアにも異なる色が塗られています。

    • $ (1,\ 1) $ と $ (1,\ 3) $ : RB
    • $ (1,\ 3) $ と $ (2,\ 2) $ : BG
    • $ (2,\ 2) $ と $ (1,\ 1) $ : GR
    • $ (2,\ 1) $ と $ (2,\ 3) $ : RB
    • $ (2,\ 3) $ と $ (1,\ 2) $ : BY
    • $ (1,\ 2) $ と $ (2,\ 1) $ : YR

    Sample Explanation 3

    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 Explanation 4

    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
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。