1-2-3 퍼즐

$N \times M$ 크기의 격자판이 주어졌다. 모든 칸에 $0$ 이상 $3$ 이하인 숫자가 적혀있다. $0$은 그 칸이 비었음을 의미한다. 예를 들어, 아래 그림은 $4 \times 4$ 크기의 격자판으로 두 개의 칸에 $2$가 적혀있고, 다른 모든 칸은 비어있다.

이때, 아래의 조건을 모두 만족하도록 비어있는 칸들, 즉, $0$이 적힌 칸들에 각각 $1$, $2$, $3$ 중 하나의 숫자를 적어보자.

1. 모든 숫자들은 왼쪽, 오른쪽, 위, 아래 네 방향에 같은 숫자가 있는 경우 하나의 그룹을 구성한다.
2. 모든 $1$은 크기 $1$인 그룹을 만들고, 모든 $2$는 크기 $2$인 그룹을 만들고, 모든 $3$은 크기 $3$인 그룹을 만들어야 한다.

예를 들어, 위의 격자판의 경우에는 다음과 같이 위 조건을 모두 만족하도록 빈 칸을 채울 수 있다.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 50$)

이어지는 $N$ 개의 줄에는 위에서 아래로 격자판을 한 줄씩 읽었을 때 정보를 나타내는 $0$ 이상 $3$ 이하인 $M$ 개의 정수가 공백으로 구분되어 주어진다.

출력 형식

총 $N$ 개의 줄에 걸쳐 답을 출력한다. 위에서 아래로 격자판을 한 줄씩 읽었을 때 정보를 나타내는 $0$ 이상 $3$ 이하인 $M$ 개의 정수를 공백으로 구분하여 출력한다.

예제

4 4
0 0 0 0
0 0 0 2
0 0 2 0
0 0 0 0

1 3 3 2
3 1 3 2
3 2 2 3
3 1 3 3

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

시뮬레이터에서 비어있는 칸들을 드래그 앤 드롭으로 이어주면 그룹을 구성할 수 있다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$ : 미션의 만점
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$: 미션마다 정해진 상수 ($0$인 칸의 개수)
• $c$: 입력에서는 $0$인 칸이 출력에서는 $0$이 아닌 칸의 개수

$P = S \times \frac{c}{\alpha}$

이후, $P$는 최종적으로 $0.1$ 단위로 버림된다.

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 격자판에 적힌 $0$이 아닌 숫자가 입력과 다른 경우 등) $P = 0$이다.

각 미션의 정보는 다음과 같다.

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설