B - Grid Repainting 4 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

H \times W のマス目で表されるキャンバスがあり、上から i (1 \leq i \leq H) 行目、左から j (1 \leq j \leq W) 列目のマスを (i, j) と表します。

最初、マス (i, j) の状態は以下のようになっています。

  • c_{i, j}=1 のとき：色 1 で塗られている
  • c_{i, j}=2 のとき：色 2 で塗られている
  • c_{i, j}=3 のとき：色 3 で塗られている
  • c_{i, j}=4 のとき：色 4 で塗られている
  • c_{i, j}=5 のとき：色 5 で塗られている
  • c_{i, j}=. のとき：まだ塗られていない

上下左右に隣り合うマスが同じ色にならないように、まだ塗られていないマスを色 1, 2, 3, 4, 5 のいずれかで塗る方法を 1 つ構成してください。ただし、既に塗られたマスを別の色で塗り替えることはできません。

制約

  • 1 \leq H, W \leq 700
  • c_{i, j} は 1、2、3、4、5、. のいずれか
  • まだ塗られていないマスが 1 つ以上存在する
  • 条件を満たす塗り方は必ず 1 つ以上存在する

入力

入力は以下の形式で標準入力から与えられます。 

H W
c_{1, 1}c_{1, 2}\ldotsc_{1, W}
c_{2, 1}c_{2, 2}\ldotsc_{2, W}
 :
c_{H, 1}c_{H, 2}\ldotsc_{H, W}

出力

マスの塗り方を以下の形式で出力してください。

ただし、d_{i, j} はすべてのマスを塗り終わった後のマス (i, j) の色とします。（1、2、3、4、5 のいずれかでなければなりません）

d_{1, 1}d_{1, 2}\ldotsd_{1, W}
d_{2, 1}d_{2, 2}\ldotsd_{2, W}
 :
d_{H, 1}d_{H, 2}\ldotsd_{H, W}

条件を満たす塗り方が複数存在する場合、そのうちどれを出力しても構いません。

入力例 1

3 3
...
...
...

出力例 1

132
313
541

出力例 1 は、以下の塗り方に対応しています。

入力例 2

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

出力例 2

1425314
2531425
3142531
4253142
5314253

出力例 2 は、以下の塗り方に対応しています。

入力例 3

1 1
.

出力例 3

4

Score : 300 points

Problem Statement

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}\ldotsc_{1, W}
c_{2, 1}c_{2, 2}\ldotsc_{2, W}
 :
c_{H, 1}c_{H, 2}\ldotsc_{H, W}

Output

Print a way to paint the squares in the following format. Here, d_{i, j} should be the color of (i, j) after painting the squares (it should be 1, 2, 3, 4, or 5).

d_{1, 1}d_{1, 2}\ldotsd_{1, W}
d_{2, 1}d_{2, 2}\ldotsd_{2, W}
 :
d_{H, 1}d_{H, 2}\ldotsd_{H, W}

If there are multiple ways to paint the squares under the condition, you may print any of them.

Sample Input 1

3 3
...
...
...

Sample Output 1

132
313
541

Sample Output 1 corresponds to the following coloring.

Sample Input 2

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

Sample Output 2

1425314
2531425
3142531
4253142
5314253

Sample Output 2 corresponds to the following coloring.

Sample Input 3

1 1
.

Sample Output 3

4