루프

시간 제한2초메모리 제한1024 MB

요약

각 2x2 정사각형의 고리 모양 유형이 주어질 때, 그 모양을 만드는 1부터 nm까지 서로 다른 정수로 이루어진 n×m 행렬을 구성합니다.

난이도: 어려움10점 중 8점
유형: 행렬, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

네 정수 $A$ , $B$ , $C$ , $D$ 가 $A < B < C < D$ 를 만족한다고 하자. 이 네 정수를 정사각형의 꼭짓점에 어떤 순서로든 놓고 $A - B - C - D - A$ 순서로 선을 그려 루프를 만든다. 정수의 배치에 따라 루프 모양이 달라지며, 모양이 같은 배치도 있다:

루프 모양은 세 가지가 가능하다:

이제 $1$ 부터 $nm$ 까지의 서로 다른 정수로 채워진 $n\times m$ 행렬을 생각하자. 이 행렬의 각 $2\times 2$ 정사각형은 꼭짓점에 정수가 놓인 정사각형으로 볼 수 있다. 앞에서와 같은 방식으로 각 정사각형마다 루프를 만든다:

이 작업의 역연산이 과제다. $(n-1)(m-1)$ 개 루프 모두의 모양 종류가 주어지면, 이 모양들을 만들어내는 $1$ 부터 $nm$ 까지의 서로 다른 정수로 채워진 $n\times m$ 행렬을 만들어야 한다.

입력

첫 줄에 두 정수 $n$ , $m$ 이 주어진다 ( $2\le n, m\le 500$ ).

다음 $n-1$ 개 줄에는 공백 없이 $m-1$ 개의 문자로 이루어진 문자열이 한 줄씩 주어진다. 각 문자는 $1$ 부터 $3$ 까지의 숫자이며, 해당 위치 루프의 모양 종류를 나타낸다.

출력

주어진 루프 모양을 만들어내는, $1$ 부터 $nm$ 까지의 서로 다른 정수로 채워진 $n\times m$ 행렬을 출력한다.

그러한 행렬이 항상 존재함은 증명되어 있다. 답이 여러 개이면 그중 아무거나 출력한다.

예제1

예제 1
입력
```
3 4
113
231
```
예상 출력
```
9 11 7 12
4 6 1 8
2 10 5 3
```