N×M 보드 완주하기

N×M 보드 위에서 하는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나뉘어 있고, 각 칸은 빈 칸이거나 장애물이다.

게임을 시작하려면 빈 칸 하나를 골라 그 위에 공을 놓아야 한다. 게임은 여러 단계로 이루어지고, 한 단계는 다음과 같다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속 굴린다.
• 공은 장애물, 보드의 경계, 이미 공이 지나간 칸을 만나기 직전 칸에서 멈춘다.

고른 방향으로 공이 한 칸도 굴러갈 수 없으면 그 방향은 고를 수 없다. 어느 방향으로도 공을 굴릴 수 없게 되면 게임이 끝나고, 그 시점에 보드의 빈 칸을 공이 모두 방문한 상태여야 한다.

보드의 상태가 주어졌을 때, 모든 빈 칸을 방문하는 데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 공을 처음 놓는 것은 이동 횟수에 세지 않는다.

입력은 여러 개의 테스트 케이스로 이루어지고, 파일의 끝에서 입력이 끝난다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 한 줄에 M개의 문자로 주어진다. 장애물은 *, 빈 칸은 .이다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

각 테스트 케이스마다 한 줄에 Case x: y 형식으로 출력한다. x는 1부터 세는 테스트 케이스 번호이고, y는 모든 빈 칸을 방문하는 최소 이동 횟수이다.

모든 빈 칸을 방문할 수 없다면 y는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.