P13481 [GCJ 2008 AMER SemiFinal] King

Alice 和 Bob 想玩一个游戏。游戏在一个有 $R$ 行 $C$ 列的棋盘上进行，总共有 $RC$ 个格子。其中一些格子已经被烧毁。 一枚国王会被放置在棋盘上的某个未烧毁的格子上，Alice 和 Bob 轮流移动国王。 每次移动时，玩家必须将国王移动到其 8 个相邻格子中的任意一个，但需满足以下两个条件： - 目标格子不能是烧毁的格子； - 国王之前从未到过目标格子。 如果某个玩家无法移动，则该玩家输掉游戏。Alice 先手。假设双方都采取最优策略，请你判断谁会获胜。

输入的第一行包含测试用例的数量 $N$。 接下来有 $N$ 组测试数据。每组测试数据的第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行，每行是一个长度为 $C$ 的字符串，表示该行的 $C$ 个格子。每个字符串只包含字符 '.'、'#' 和 'K'： - '#' 表示该格子已被烧毁； - '.' 表示该格子未被烧毁且未被占据； - 'K' 表示国王初始所在的格子。 每个测试用例中只会有一个 'K' 字符。

对于每个测试用例，输出一行，格式为 "Case #$X$: "（其中 $X$ 是测试用例编号，从 1 开始），后接 A（如果 Alice 获胜）或 B（如果 Bob 获胜）。

**数据范围** - $1 \leqslant N \leqslant 100$ **小数据范围（7 分，测试点 1 - 可见）** - 时间限制：~~30~~ 3 秒。 - $1 \leqslant R, C \leqslant 4$ **大数据范围（38 分，测试点 2 - 隐藏）** - 时间限制：~~180~~ 36 秒。 - $1 \leqslant R, C \leqslant 15$ 由 ChatGPT 4.1 翻译