Clearing an N×M Board

There is a game played on an N×M board. The board is divided into squares of size 1×1, and every square is either empty or an obstacle.

To start the game you pick one empty square and place a ball on it. The game runs in steps, and one step works like this.

• Choose one of the four directions up, down, right, left, then keep rolling the ball that way.
• The ball stops on the square right before an obstacle, the edge of the board, or a square the ball has already passed through.

If the ball cannot roll even one square in a direction, that direction is not available. The game ends once no direction is available, and at that moment the ball must have visited every empty square of the board.

Given the state of the board, write a program that finds the minimum number of moves needed to visit every empty square. Placing the ball at the start does not count as a move.

The input holds several test cases and ends at the end of the file.

The first line of each test case has N and M, the size of the board. N is the height, M is the width, and both are natural numbers no larger than 30. The next N lines give the state of the board, M characters per line. An obstacle is * and an empty square is ..

No board in the input consists only of obstacles.

For each test case print one line in the form Case x: y. Here x is the test case number counting from 1, and y is the minimum number of moves that visits every empty square.

If the ball cannot visit every empty square, y is -1. The number of possible rolling paths does not exceed 1,000,000.