소금과 후추 (Small)

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

요약
M×N 밝기 행렬과 홀수 창 크기 W가 주어질 때, 모든 W×W 창의 중앙값을 출력한다.
난이도

쉬움10점 중 3점

유형
배열, 정렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

갑과 을은 사귀는 사이다. 어느 저녁 둘은 크림 치즈 스파게티를 먹으러 식당에 들어갔다. 먹음직스러운 스파게티가 예뻐 보인 갑은 스마트폰으로 사진을 찍었고, 그 사진을 SNS에 올리려다가 스파게티 위에 뿌려진 소금과 후추를 발견했다.

갑은 사진 속 소금과 후추가 마음에 들지 않아 을에게 지워줄 수 있냐고 물었다. 을은 자신 있게 해주겠다고 답하고 가방에서 종이와 펜을 꺼내 문제를 다음과 같이 정리했다.

  • 사진을 나타내는 M×NM \times N 행렬 AA가 입력으로 주어진다. 각 원소는 픽셀 하나의 밝기이며, 0이 가장 어둡고 KK가 가장 밝다.
  • 또 다른 입력으로 정수 WW가 주어진다. WW로 행렬 BB를 다음과 같이 정의한다.
    • B[i][j]=median(A[i+x][j+y])B[i][j] = \mathrm{median}(A[i+x][j+y])
    • 이때 1≤i≤M−W+11 \le i \le M-W+1, 1≤j≤N−W+11 \le j \le N-W+1, 0≤x,y<W0 \le x, y < W이다.
    • A[i+x][j+y]A[i+x][j+y]는 행렬 AA의 i+xi+x행 j+yj+y열에 있는 원소이고, median은 중앙값이다.
  • 행렬 AA와 정수 WW로 행렬 BB를 구한다.

행렬 AA와 WW로 행렬 BB를 만드는 과정

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

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

입력

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

둘째 줄부터 MM개의 줄에 걸쳐 각 줄마다 0 이상 KK 이하의 정수가 NN개씩 주어진다. 위에서 ii번째 줄의 jj번째 정수는 행렬 AA의 ii행 jj열 원소다.

출력

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

예제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