Problem
Alice and Bob want to play a game. The game is played on a chessboard with R rows and C columns, for a total of RC squares. Some of these squares are burned.
A king will be placed on an unburned square of the board, and Alice and Bob will make successive moves with the king.
In a move, the player must move the king to any of its 8 neighboring squares, with the following two conditions:
- The destination square must not be burned
- The king must never have been in the destination square before.
If a player can't make a move, he or she loses the game. Alice will move first; you need to determine who will win, assuming both players play optimally.
Input
The first line of input gives the number of cases, N. N test cases follow. The first line of each case will contain two integers, R and C. The next R lines will contain strings of length C, representing the C squares of each row. Each string will contain only the characters '.', '#' and 'K':
- '#' means the square is burned;
- '.' means the square is unburned, and unoccupied; and
- 'K' means the king is in that cell at the beginning of the game.
There will be only one 'K' character in each test case.
Output
For each test case, output one line containing "Case #X: " (where X is the case number, starting from 1) followed by A if Alice wins, or B if Bob wins.
Limits
Memory limit: 1GB.
1 ≤ N ≤ 100
Small dataset (Test set 1 - Visible; 7 Points)
Time limit: 30 5 seconds.
1 ≤ R, C ≤ 4
Large dataset (Test set 2 - Hidden; 38 Points)
Time limit: 180 30 seconds.
1 ≤ R, C ≤ 15
Sample
2 2 2 K. .# 4 2 K# .# .# .#
Case #1: B Case #2: A