Grid Repainting 4

AtCoder

IDarc131_b

Time2000ms

Memory256MB

Difficulty—

We have a canvas represented as a $H \times W$ grid. Let $(i, j)$ denote the square at the $i$\-th row $(1 \leq i \leq H)$ from the top and $j$\-th column $(1 \leq j \leq W)$ from the left. Initially, $(i, j)$ is in the following state. * If $c_{i, j}=$`1`: painted in Color 1. * If $c_{i, j}=$`2`: painted in Color 2. * If $c_{i, j}=$`3`: painted in Color 3. * If $c_{i, j}=$`4`: painted in Color 4. * If $c_{i, j}=$`5`: painted in Color 5. * If $c_{i, j}=$`.`: not yet painted. Create a way to paint each unpainted square in Color 1, 2, 3, 4, or 5 so that no two horizontally or vertically adjacent squares have the same color. It is not allowed to change the color of a square that is already painted. ## Constraints * $1 \leq H, W \leq 700$ * $c_{i, j}$ is `1`, `2`, `3`, `4`, `5`, or `.`. * At least one square is unpainted. * There is at least one way to paint the squares under the condition. ## Input Input is given from Standard Input in the following format: $H$ $W$ $c_{1, 1}$$c_{1, 2}$$\ldots$$c_{1, W}$ $c_{2, 1}$$c_{2, 2}$$\ldots$$c_{2, W}$ $:$ $c_{H, 1}$$c_{H, 2}$$\ldots$$c_{H, W}$ [samples]

Samples

Input #1

3 3
...
...
...

Output #1

132
313
541

Sample Output 1 corresponds to the following coloring.
![image](https://img.atcoder.jp/arc131/35bb8a98465fbb2c889ea532d0985ff0.png)

Input #2

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

Output #2

1425314
2531425
3142531
4253142
5314253

Sample Output 2 corresponds to the following coloring.
![image](https://img.atcoder.jp/arc131/a2fc3903965fd871d25e905fb95dbc6a.png)

Input #3

1 1
.

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Grid Repainting 4",
    "description": {
      "content": "We have a canvas represented as a $H \\times W$ grid. Let $(i, j)$ denote the square at the $i$\\-th row $(1 \\leq i \\leq H)$ from the top and $j$\\-th column $(1 \\leq j \\leq W)$ from the left. Initially,",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc131_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a canvas represented as a $H \\times W$ grid. Let $(i, j)$ denote the square at the $i$\\-th row $(1 \\leq i \\leq H)$ from the top and $j$\\-th column $(1 \\leq j \\leq W)$ from the left.\nInitially,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments