중앙값 필터
시간 제한8초메모리 제한512 MB
3x3 중앙값 필터를 적용한 흑백 이미지가 주어질 때, 원본 이미지가 가질 수 있는 검은 픽셀 수의 최댓값과 최솟값의 차이를 구하고, 가능한 원본이 없으면 Impossible을 출력한다.
문제
중앙값 필터는 이미지, 소리, 그 밖의 신호에서 잡음을 줄이는 데 쓰이는 비선형 디지털 필터이다. 입력의 각 표본을 윈도를 통해 검사하고, 윈도 안에 있는 표본들의 중앙값을 출력한다. 대략 말하자면 윈도는 대상 표본과 그 앞뒤의 표본을 포함하는 구간이고, 값들의 중앙값은 그 값들을 오름차순(또는 내림차순)으로 늘어놓았을 때 가운데에 오는 값이다.
흑백 래스터 이미지에 쓰이는 전형적인 중앙값 필터를 살펴보자. 이 필터는 대상 픽셀과 인접한 여덟 픽셀을 포함하는 3 × 3 윈도를 사용한다. 필터는 이 3 × 3 윈도로 각 픽셀을 차례로 검사하고, 아홉 픽셀 값의 중앙값, 즉 다섯 번째로 작은(또는 큰) 픽셀 값을 해당 픽셀에 출력한다. 흑백 이미지에서는 가능한 픽셀 값이 검정과 흰색 두 가지뿐이므로, 출력은 곧 다수인 픽셀 값이라는 점에 유의하자. 아래 그림은 필터가 동작하는 방식을 보여준다.
참고: 옅게 칠한 픽셀의 색은 영역 바깥에 따라 달라진다.
이미지의 가장자리는 인접한 픽셀이 없어서 특별히 처리해야 한다. 이 문제에서는 아래 그림처럼 가장자리의 픽셀을 반복해서 원본 이미지를 확장한다. 즉, 없는 픽셀은 원본 이미지에서 가장 가까운 사용 가능한 픽셀과 같은 값을 가진다.
참고: 문자 ‘a’부터 ‘f’는 픽셀 값을 나타낸다.
필터를 적용한 이미지를 읽고, 가능한 모든 원본 이미지 가운데 검정 픽셀의 수가 가장 많고 가장 적은 원본 이미지를 찾아 검정 픽셀 수의 차이를 보고하는 프로그램을 작성하시오.
입력
입력은 여러 테스트 케이스로 이루어진다.
각 테스트 케이스의 첫 줄에는 이미지의 너비와 높이를 나타내는 두 정수 W와 H (1 ≤ W, H ≤ 8)가 주어진다. 그다음 H개의 줄이 필터를 적용한 이미지를 나타낸다. i번째 줄은 i번째 주사선을 나타내며 정확히 W개의 문자로 이루어지고, 각 문자는 ‘#’(검정) 또는 ‘.’(흰색)이다.
입력은 두 개의 0으로 이루어진 줄로 끝난다.
출력
각 테스트 케이스마다 케이스 번호와 검정 픽셀 수의 차이를 한 줄에 출력한다. 주어진 필터 적용 이미지에 대해 가능한 원본 이미지가 없으면 대신 “Impossible”을 출력한다.
출력 예시에 나온 형식을 따르시오.