흐릿한 이미지 복원하기

이미지 흐림(blur)은 촬영 대상이 카메라 초점에서 벗어났을 때 발생합니다. 흐려진 이미지만 주어졌을 때 원본 이미지를 복원하는 것은 영상 처리에서 매우 흥미로운 주제이며, 이 과정을 디블러링(deblurring)이라고 합니다. 이 문제에서 여러분이 해결할 작업이 바로 이것입니다.

이 문제에서 모든 이미지는 색이 없는 회색조(grey-scale)입니다. 이미지는 실수로 이루어진 2차원 행렬로 표현되며, 각 칸은 해당 픽셀의 밝기를 나타냅니다. 수학적으로 엄밀하지는 않지만, 흐려진 이미지는 각 픽셀을 그 픽셀로부터의 맨해튼 거리(Manhattan distance)†가 고정값 $D$ 이하인 모든 픽셀(자기 자신 포함)의 평균으로 바꾼 것으로 설명할 수 있습니다. 다음은 흐림 거리 $D = 1$일 때 $3 \times 3$ 이미지의 흐림을 계산하는 예입니다.

흐려진 이미지가 주어졌을 때, 위 방식 그대로 흐려졌다고 가정하고 원본 이미지를 복원하세요.

† 두 점 사이의 맨해튼 거리(택시 거리라고도 함)는 각 좌표 차이의 절댓값을 모두 더한 값입니다. 즉, 두 픽셀 $(r_1, c_1)$과 $(r_2, c_2)$ 사이의 맨해튼 거리는 $|r_1 - r_2| + |c_1 - c_2|$ 입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스는 $H + 1$개의 줄로 주어집니다. 첫 줄에는 세 개의 음이 아닌 정수 $W$, $H$, $D$가 주어지며, 각각 흐려진 이미지의 너비, 높이, 흐림 거리를 의미합니다. 여기서 $1 \le W, H \le 10$ 이고 $D \le \min(W/2, H/2)$ 입니다. 이어지는 $H$개의 줄에는 흐려진 이미지의 각 픽셀 밝기가 주어집니다. 각 줄에는 $W$개의 음이 아닌 실수가 소수점 둘째 자리까지 주어지며, 모든 값은 $100$ 미만입니다.

케이스와 케이스 사이에는 공백만으로 이루어진 줄이 0개 이상 나타날 수 있습니다. 입력의 마지막 줄은 세 개의 $0$입니다.

각 테스트 케이스에 대해, 흐림을 제거한 이미지를 원본과 같은 크기의 실수 행렬로 출력하세요($H$개의 줄, 각 줄에 $W$개의 값). 각 원소는 소수점 둘째 자리까지 반올림하고, 너비 $8$의 칸에 오른쪽 정렬하여 출력합니다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣고, 마지막 테스트 케이스 뒤에는 빈 줄을 출력하지 않습니다. 모든 테스트 케이스에는 유일한 해가 존재함이 보장됩니다.