파리채
면접 대비시간 제한1초메모리 제한64 MB
한 변이 K인 정사각형 파리채를 놓아 테두리를 제외한 내부 파리가 가장 많아지는 위치를 찾아 개수와 테두리를 그린 그림을 출력합니다.
문제
마린은 시간이 나면 창밖을 내다본다. 그 창문에는 파리 몇 마리가 앉아 먼 곳을 바라보고 있다. 마린은 정사각형 파리채를 들고 와서, 한 번 내리쳐 파리를 최대 몇 마리까지 잡을 수 있을지 궁금해졌다.
창문 사진의 크기는 픽셀이고, 파리채의 한 변 길이는 픽셀이다. 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 구하고, 그렇게 잡을 수 있는 파리채 위치 하나를 사진 위에 표시하라.
입력
첫째 줄에 사진의 크기와 파리채의 한 변 길이를 나타내는 세 정수 , , 가 주어진다 (, ).
다음 개 줄에는 각각 개의 문자가 주어져 창문 사진을 나타낸다. 파리가 앉은 픽셀은 *, 빈 픽셀은 .이다. 파리채로 잡을 수 있는 파리가 적어도 한 마리 있다.
출력
첫째 줄에 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 출력한다.
이어서 개 줄에 파리채 위치를 표시한 사진을 출력한다. 파리채의 가로 변은 -, 세로 변은 |, 네 모서리는 +로 나타내며, 이 문자는 원래 픽셀 위에 덮어 쓴다.
파리채는 창문 안에 완전히 들어가야 한다. 변 위에 있는 파리는 날아갈 시간이 충분하므로, 파리채 내부에 엄격히 들어 있는 파리만 잡힌다. 행과 열을 부터 셀 때 왼쪽 위 모서리가 인 파리채는 행 부터 까지, 열 부터 까지에 있는 파리를 잡는다.
최대 마리 수를 잡는 위치가 여럿이면 왼쪽 위 모서리의 행 번호가 가장 작은 위치를 표시하고, 그런 위치도 여럿이면 그중 열 번호가 가장 작은 위치를 표시한다.