만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

파리채

면접 대비

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

요약
한 변이 K인 정사각형 파리채를 놓아 테두리를 제외한 내부 파리가 가장 많아지는 위치를 찾아 개수와 테두리를 그린 그림을 출력합니다.
난이도

쉬움10점 중 3점

유형
누적 합, 행렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

마린은 시간이 나면 창밖을 내다본다. 그 창문에는 파리 몇 마리가 앉아 먼 곳을 바라보고 있다. 마린은 정사각형 파리채를 들고 와서, 한 번 내리쳐 파리를 최대 몇 마리까지 잡을 수 있을지 궁금해졌다.

창문 사진의 크기는 R×SR \times S 픽셀이고, 파리채의 한 변 길이는 KK 픽셀이다. 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 구하고, 그렇게 잡을 수 있는 파리채 위치 하나를 사진 위에 표시하라.

입력

첫째 줄에 사진의 크기와 파리채의 한 변 길이를 나타내는 세 정수 RR, SS, KK가 주어진다 (3≤K≤R≤1003 \le K \le R \le 100, K≤S≤100K \le S \le 100).

다음 RR개 줄에는 각각 SS개의 문자가 주어져 창문 사진을 나타낸다. 파리가 앉은 픽셀은 *, 빈 픽셀은 .이다. 파리채로 잡을 수 있는 파리가 적어도 한 마리 있다.

출력

첫째 줄에 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 출력한다.

이어서 RR개 줄에 파리채 위치를 표시한 사진을 출력한다. 파리채의 가로 변은 -, 세로 변은 |, 네 모서리는 +로 나타내며, 이 문자는 원래 픽셀 위에 덮어 쓴다.

파리채는 창문 안에 완전히 들어가야 한다. 변 위에 있는 파리는 날아갈 시간이 충분하므로, 파리채 내부에 엄격히 들어 있는 파리만 잡힌다. 행과 열을 00부터 셀 때 왼쪽 위 모서리가 (i,j)(i, j)인 파리채는 행 i+1i+1부터 i+K−2i+K-2까지, 열 j+1j+1부터 j+K−2j+K-2까지에 있는 파리를 잡는다.

최대 마리 수를 잡는 위치가 여럿이면 왼쪽 위 모서리의 행 번호가 가장 작은 위치를 표시하고, 그런 위치도 여럿이면 그중 열 번호가 가장 작은 위치를 표시한다.

예제3

  1. 예제 1

    입력
    3 5 3
    .....
    .*.*.
    .....
    
    예상 출력
    1
    +-+..
    |*|*.
    +-+..
    
  2. 예제 2

    입력
    7 6 4
    ......
    .*.*.*
    ......
    .*.*..
    ..*...
    ..*...
    *....*
    
    예상 출력
    2
    ......
    .*.*.*
    +--+..
    |*.|..
    |.*|..
    +--+..
    *....*
    
  3. 예제 3

    입력
    9 9 6
    ***......
    ......*.*
    .*....*..
    ..*...*..
    ..*.*....
    ..*....*.
    .....*...
    .*...***.
    .........
    
    예상 출력
    6
    ***......
    ......*.*
    .*....*..
    ..*+----+
    ..*|*...|
    ..*|...*|
    ...|.*..|
    .*.|.***|
    ...+----+