소금과 후추 (Large)

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

요약
행렬의 각 W x W 창에서 W^2개 픽셀 값의 중앙값을 구해 출력한다.
난이도

보통10점 중 6점

유형
슬라이딩 윈도우, 정렬, 행렬
정답자
아직 제출이 없습니다

문제

갑은 저녁으로 나온 크림치즈 스파게티 사진을 찍었다. 사진 속 파스타 위에 흩뿌려진 소금과 후추가 눈에 거슬린 갑은, 을에게 이 얼룩을 지워 달라고 부탁했다. 을은 가방에서 종이와 펜을 꺼내 문제를 이렇게 정리했다.

  • 사진을 나타내는 M×NM \times N 행렬 AA가 입력으로 주어진다. 행렬의 각 원소는 픽셀 하나의 밝기이고, 00이 가장 어두운 값, KK가 가장 밝은 값이다.
  • 정수 WW가 함께 주어진다. WW로 행렬 BB를 다음과 같이 정의한다.

B[i][j]=median(A[i+x][j+y]),1≤i≤M−W+1,  1≤j≤N−W+1,  0≤x,y<WB[i][j] = \mathrm{median}(A[i+x][j+y]), \quad 1 \le i \le M-W+1, \; 1 \le j \le N-W+1, \; 0 \le x, y < W

여기서 A[i+x][j+y]A[i+x][j+y]는 행렬 AA의 i+xi+x행 j+yj+y열에 있는 원소다. 즉 B[i][j]B[i][j]는 AA에서 ii행 jj열을 왼쪽 위 모서리로 삼는 W×WW \times W 정사각 구간에 들어 있는 W2W^2개 값의 중앙값이다.

  • 주어진 행렬 AA와 정수 WW로 행렬 BB를 구한다.

그림: 행렬 AA와 WW로 행렬 BB를 만드는 과정.

을은 노트북을 펼치고 프로그램을 짜기 시작했지만 잘 풀리지 않았고, 그사이 스파게티는 붇기 시작했다. 스파게티가 다 붇기 전에 을 대신 이 문제를 푸는 프로그램을 작성하라.

중앙값은 주어진 값을 크기 순으로 정렬했을 때 한가운데에 놓이는 값이다. 예를 들어 1, 2, 3, 3, 100 다섯 값에서는 3이 한가운데에 있으므로 중앙값이 3이다. WW가 홀수라서 W2W^2도 홀수이고, 중앙값은 언제나 하나로 정해진다.

입력

첫째 줄에 행렬의 크기를 나타내는 정수 MM과 NN (1≤M,N≤3001 \le M, N \le 300), 최대 밝기 KK (1≤K≤100,0001 \le K \le 100{,}000), 정수 WW (1≤W≤min⁡(M,N)1 \le W \le \min(M, N))가 공백으로 구분되어 차례로 주어진다. WW는 홀수다.

둘째 줄부터 MM개 줄에 걸쳐 각 줄마다 NN개의 정수가 주어진다. 1+i1+i번째 줄의 jj번째 정수는 행렬 AA의 ii행 jj열 원소이며, 00 이상 KK 이하다.

출력

M−W+1M-W+1개 줄에 걸쳐 행렬 BB를 출력한다. 각 줄에는 N−W+1N-W+1개의 정수를 공백 하나로 구분해 출력한다.

힌트

WW가 11이면 각 구간에 값이 하나뿐이므로 BB는 AA와 같다.

WW가 33이고 구간에 5, 1, 2, 12, 10, 3, 8, 12, 19가 들어 있다고 하자. 정렬하면 1, 2, 3, 5, 8, 10, 12, 12, 19이고 다섯 번째 값이 한가운데이므로 중앙값은 8이다.

예제3

  1. 예제 1

    입력
    3 3 10 1
1 2 3
4 5 6
7 8 9
    예상 출력
    1 2 3
4 5 6
7 8 9

  2. 예제 2

    입력
    3 3 10 3
1 2 3
4 5 6
7 8 9
    예상 출력
    5

  3. 예제 3

    입력
    5 5 20 3
5 1 2 8 10
12 10 3 20 7
8 12 19 18 15
17 19 2 5 13
11 2 4 14 16
    예상 출력
    8 10 10
12 12 13
11 12 14