이미지 필터

면접 대비

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

요약

높이맵의 각 픽셀마다 다섯 필터 중 절대 오차가 가장 작은 필터와 차이값을 고르고, 동점이면 사전순으로 가장 작은 쌍을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 구현, 그리디
정답자: 아직 제출이 없습니다

문제

알고리즘 대회를 준비할 때 출제진은 서로 데이터를 주고받으며 검증한다. 높이맵(heightmap)을 활용한 문제를 내던 B모씨는 데이터를 모두 만들었고 만족했다.

남은 일은 데이터를 검증하는 절차였는데, 여기서 문제를 발견했다. 높이맵을 만들 때 별생각 없이 16비트 그레이스케일 비트맵으로 저장했더니 파일이 너무 커서, 출제진끼리 실시간으로 주고받기 어려웠다.

이를 해결하려고 필터를 사용하는 비트맵 압축 방식을 설계했다. 압축은 각 칸을 차례로 처리한다. $p$ 행 $q$ 열의 높이를 $H_{p,q}$ 라 하자. 압축할 칸이 $r$ 행 $c$ 열에 있을 때, 다음과 같이 정의한다.

$A = H_{r,c-1}$ , 해당 위치에 칸이 없으면 $0$
$B = H_{r-1,c}$ , 해당 위치에 칸이 없으면 $0$
$C = H_{r-1,c-1}$ , 해당 위치에 칸이 없으면 $0$

압축된 이미지의 각 높이는 아래 표의 다섯 가지 필터 중 하나로 표현한다. 압축된 각 칸은 필터 번호와, 그 필터로 계산한 예측값과의 차이로 나타낸다.

번호	필터 예측값
$0$	$0$
$1$	$A$
$2$	$B$
$3$	$(A + B)$ 를 $2$ 로 나눈 몫
$4$	$A + B - C$

예를 들어 다음과 같은 $2$ 행 $2$ 열의 높이맵이 있다고 하자.

6 4
2 1

오른쪽 아래의 1을 표현하는 경우를 살펴보면 다음과 같다.

0번 필터는 예측값과의 차이가 $1 - 0 = 1$
1번 필터는 예측값과의 차이가 $1 - 2 = -1$
2번 필터는 예측값과의 차이가 $1 - 4 = -3$
3번 필터는 예측값과의 차이가 $1 - (2 + 4)/2 = -2$
4번 필터는 예측값과의 차이가 $1 - (2 + 4 - 6) = 1$

압축된 전체 이미지는 가능한 모든 필터 사용 방법 중에서 예측값과의 차이의 절댓값의 총합을 최소화해야 한다. 그러한 방법이 여러 가지라면, 압축된 각 칸을 구성하는 (필터 번호, 차이) 쌍을 왼쪽 위에서부터 열 방향으로 순서대로 나열했을 때 사전순으로 최소인 방법을 선택한다. 이와 같은 압축을 수행하는 프로그램을 작성하라.

입력

입력은 $T$ 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 높이맵의 크기 $R$ , $C$ ( $1 \le R \le 100$ , $1 \le C \le 100$ )가 공백으로 구분되어 주어진다. 높이맵은 $R$ 행 $C$ 열이다. 이후 $R$ 개의 줄에 높이맵 픽셀의 값을 나타내는 $C$ 개의 정수 $H_{i,j}$ ( $0 \le H_{i,j} < 2^{16}$ )가 공백을 사이에 두고 주어진다.

출력

각 테스트 케이스마다 $R$ 개의 줄을 출력한다. 각 줄에는 적용한 필터의 번호와 예측값과의 차이를 나타내는 정수를 공백으로 구분하여 $C$ 쌍 출력한다.

예제1

예제 1

입력

3
2 2
6 4
2 1
3 3
0 0 0
0 100 0
0 0 0
4 5
0 0 0 0 0
0 100 50 50 0
0 50 100 50 0
0 0 0 0 0

예상 출력

0 6 3 1
3 -1 0 1
0 0 0 0 0 0
0 0 0 100 0 0
0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 100 3 0 1 0 0 0
0 0 3 0 1 50 2 0 0 0
0 0 0 0 0 0 0 0 0 0