Nowruz 10

이제 며칠 뒤면 Nowruz(페르시아 새해)다. 할아버지는 가족을 정원에 초대했다. 손님 중에는 아이가 $k$명 있다. 아이들이 더 즐겁게 놀 수 있도록, 할아버지는 숨바꼭질 놀이를 하려고 한다.

정원은 단위 칸 $m \times n$ 격자로 나타낼 수 있다. 일부 칸(0개일 수도 있다)은 돌로 막혀 있고, 나머지 칸을 자유 칸이라고 한다. 두 칸이 변을 공유하면 이웃이라고 한다. 즉 각 칸에는 가로 방향으로 두 개, 세로 방향으로 두 개, 최대 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는 대문자여야 한다.)