2490. King

单点时限: 2.0 sec

内存限制: 256 MB

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.

输入格式

The first line of input gives the number of cases, N(1 ≤ N ≤ 100).

N test cases follow. The first line of each case will contain two integers, R and C(1 ≤ R, C ≤ 15 ). 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.

输出格式

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.

样例

Input
2
2 2
K.
.#
4 2
K#
.#
.#
.#
Output
Case #1: B
Case #2: A

0 人解决,1 人已尝试。

0 份提交通过,共有 2 份提交。

9.9 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,10 月前.

最后提交: 3 年,7 月前.

来源: GCJ 2008

题目标签