28345번 - Image Filter

알고리즘 대회를 준비할 때면, 출제진은 서로 데이터를 교환하고 검증하는 작업을 거치게 된다. 높이맵 (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$

로 정의하자. 압축된 이미지에서 모든 높이는 다음 표에 기술한 다섯 가지 필터 중 하나를 사용해 표현하게 된다. 압축된 칸은 필터 번호와 그 필터 번호로 계산해 낸 예측값과의 차이로 표현된다.

예를 들어 다음과 같은 $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 ≤ R ≤ 100$, $1 ≤ C ≤ 100$)가 공백으로 구분되어 주어진다. 높이맵의 크기는 $R$행 $C$열이다. 이후 $R$개의 줄에, 높이맵의 픽셀의 값을 나타내는 $C$개의 정수 $H_{i,j}$ ($0 ≤ H_{i,j} < 2^{16}$)들이 빈 칸을 사이에 두고 주어진다.

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