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