Nowruz 4

페르시아 새해인 Nowruz가 며칠 남지 않았고, 할아버지는 가족을 정원에 초대했다. 손님 중에는 아이가 $k$명 있다. 아이들이 더 재미있게 놀 수 있도록 할아버지는 숨바꼭질 놀이를 열려고 한다.

정원은 $m \times n$개의 단위 정사각형으로 이루어진 격자로 나타낼 수 있다. 일부 칸은 바위로 막혀 있을 수 있고(하나도 없을 수도 있다), 나머지 칸을 자유 칸이라고 한다. 두 칸이 변을 공유하면 두 칸은 이웃이라고 한다. 즉 각 칸에는 가로 방향으로 두 개, 세로 방향으로 두 개, 최대 4개의 이웃이 있다. 할아버지는 정원을 미로로 만들려고 한다. 이를 위해 자유 칸에 덤불을 심어 막을 수 있다. 덤불을 심은 칸은 더 이상 자유 칸이 아니다.

미로는 다음 성질을 만족해야 한다. 미로의 자유 칸 $a$와 $b$의 모든 쌍에 대해, 두 칸 사이에 단순 경로가 정확히 하나 있어야 한다. 칸 $a$와 $b$ 사이의 단순 경로란 첫 번째 칸이 $a$, 마지막 칸이 $b$이고 모든 칸이 서로 다르며 연속한 두 칸이 서로 이웃인 자유 칸의 나열이다.

아이는 그 칸이 자유 칸이고 자유 이웃이 정확히 하나일 때에만 그 칸에 숨을 수 있다. 두 아이가 같은 칸에 숨을 수는 없다.

정원의 지도가 입력으로 주어진다. 할아버지가 아이를 많이 숨길 수 있는 미로를 만들도록 도와야 한다.

이 문제는 부분 점수가 있는 출력 전용 문제다. 할아버지의 정원을 나타내는 입력 파일 $10$개가 주어진다. 각 입력 파일마다 미로의 지도를 담은 출력 파일을 제출해야 한다. 각 출력 파일에 대해서는 그 미로에 숨을 수 있는 아이의 수에 따라 점수를 받는다.

이 문제에서는 소스 코드를 제출하지 않는다.

각 입력 파일은 정원을 나타내는 하나의 격자와 할아버지가 초대한 아이의 수 $k$를 담고 있다. 형식은 다음과 같다.

• $1$번째 줄: $\;\; m \;\; n \;\; k$

• $1+i$번째 줄 ($1 \leq i \leq m$): 격자의 $i$번째 행으로, 다음 문자로 이루어진 길이 $n$의 문자열이다(공백 없음).

  • '.': 자유 칸,
  • '#': 바위.

• $i$번째 줄 ($1 \leq i \leq m$): 미로(덤불을 심은 뒤의 정원)의 $i$번째 행이다. 다음 문자로 이루어진 길이 $n$의 문자열이다(공백 없음).

  • '.': 자유 칸,
  • '#': 바위,
  • 'X': 덤불. (문자 X는 대문자여야 한다.)