게임 맵

Vasya는 여전히 컴퓨터 게임을 좋아하고, 지금도 게임 테스터로 일하고 있다. 직장에서 조금이라도 흥미로운 일을 할 수 있다는 기대는 거의 버렸다. 창의력을 발휘하려고 동료 Petya, Kolya와 함께 취미 프로젝트를 진행하고 있다. Petya는 훌륭한 인디 게임이 많고, 작은 팀도 이 분야에서 잘할 수 있다고 Vasya에게 말했다. 그러나 그 말이 전부 사실은 아니다. 인디 게임 중 몇 퍼센트가 인기를 얻는지, 완성되는 프로젝트가 몇 개인지는 말하지 않았다.

새 게임은 인기 있는 로그라이크 장르다. 수염을 기른 Kolya는 Vasya의 말을 계속 바로잡는다. 정확히는 로그라이트나 로그라이크라이크라고 해야 한다는 것이다. 로그라이크의 가장 중요한 요소 중 하나는 무작위로 생성되는 게임 월드다. 실행할 때마다 새로운 모험이 펼쳐져야 "Losing is fun"이라는 모토가 살아난다. 두 친구는 지금 게임의 월드 맵 생성을 만들고 있다.

게임은 동굴에서 진행된다. 월드 맵은 칸으로 이루어진 직사각형 격자다. 각 칸은 플레이어가 통과해야 하는 레벨이 있어 통과 가능하거나, 통과 불가능하며 아무것도 없다. 플레이어는 왼쪽 위 모서리 칸에서 시작하며, 이 칸은 반드시 통과 가능해야 한다. 레벨을 끝낸 플레이어는 인접한 칸이 통과 가능하면 아래 또는 오른쪽으로 이동할 수 있다. 격자의 마지막 행이나 마지막 열에 있을 때 플레이어는 격자 밖으로 나갈 수 있다. 이렇게 하면 게임이 끝나고 플레이어가 이긴다.

균형을 맞추기 위해 Petya는 맵에 두 가지 제한을 더 두었다.

1. 플레이어는 시작 칸에서 통과 가능한 각 칸에 오직 하나의 경로로 도달할 수 있다.
2. 플레이어는 통과 가능한 어떤 칸에서 시작하더라도 게임을 끝낼 수 있다. 다만 그 방법은 여러 가지일 수 있다.

Kolya는 이 게임의 수석 프로그래머이며 생성 코드를 직접 작성한다. 그는 무작위로 생성한 격자가 이 조건을 거의 만족하지 않는다는 사실을 알아챘다. 그래서 격자 칸 일부만 무작위로 생성하고, 나머지는 <<indefinite>> 상태로 둔다. 다음으로 나머지 칸의 내용을 정하는 알고리즘을 돌려 결과 맵이 모든 조건을 만족하게 해야 한다. 게임의 콘텐츠를 늘리기 위해 알고리즘은 통과 가능한 칸의 수를 최대로 해야 한다.

문제는 Kolya가 알고리즘 프로그래밍에 능숙하지 않아 마지막 단계를 혼자서 구현할 수 없다는 것이다. 두 친구의 꿈이 이루어지도록 도와주자!

첫 줄에는 게임 필드의 크기를 나타내는 두 정수 H와 W가 주어진다. H는 행의 수, W는 열의 수다 ($1 \le H, W \le 18$).

이어서 H줄에 걸쳐 각 줄마다 W개의 문자로 필드의 내용이 주어진다. 통과 가능한 칸은 마침표 '.', 통과 불가능한 칸은 문자 'X', 미정인 칸은 물음표 '?'로 표시한다.

필드를 올바른 상태로 정할 수 없으면 -1을 출력한다.

그렇지 않으면 첫 줄에 정해진 필드의 통과 가능한 칸 수 K를 출력한다. 이 수는 가능한 한 커야 한다. 이어서 입력과 같은 형식으로, 물음표 없이 정해진 필드를 출력한다.

최적해가 여러 개라면 그중 아무거나 출력해도 된다.