AT_abc229_h [ABC229H] Advance or Eat

题目描述

有一个 $N$ 行 $N$ 列的网格，每个格子中要么放有一个白色棋子，要么放有一个黑色棋子，要么为空。
从上往下第 $i$ 行，从左往右第 $j$ 列的格子的状态用 $S_{i,j}$ 表示，W 表示放有白色棋子，B 表示放有黑色棋子，. 表示该格为空。

高桥君和すぬけ君进行一场游戏。高桥君先手，双方轮流进行操作。

在高桥君的回合，他可以选择以下两种操作之一：

• 选择一个上方有空格的白色棋子，并将其向上移动一格；
• 吃掉任意一个黑色棋子。

在すぬけ君的回合，他可以选择以下两种操作之一：

• 选择一个上方有空格的黑色棋子，并将其向上移动一格；
• 吃掉任意一个白色棋子。

无法进行操作的一方判负。当双方都采取最优策略时，谁会获胜？

注意，“将棋子向上移动”是指将第 $i$ 行第 $j$ 列的棋子移动到第 $i-1$ 行第 $j$ 列。
高桥君和すぬけ君从同一方向观察棋盘，“上”对两人来说方向相同。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_{1,1}S_{1,2}\ldots S_{1,N}$
$S_{2,1}S_{2,2}\ldots S_{2,N}$
$\vdots$
$S_{N,1}S_{N,2}\ldots S_{N,N}$

输出格式

如果高桥君获胜，输出 Takahashi；如果すぬけ君获胜，输出 Snuke。

输入输出样例 #1

输入 #1

3
BB.
.B.
...

输出 #1

Takahashi

输入输出样例 #2

输入 #2

2
..
WW

输出 #2

Snuke

输入输出样例 #3

输入 #3

4
WWBW
WWWW
BWB.
BBBB

输出 #3

Snuke

说明/提示

限制条件

• $1 \leq N \leq 8$
• $N$ 为整数
• $S_{i,j}$ 只可能为 W、B 或 .

样例解释 1

一开始高桥君吃掉第 $1$ 行第 $1$ 列的黑色棋子后，棋盘如下所示：

.B.
.B.
...

此时すぬけ君无法进行任何操作，因此高桥君获胜。

注意，不能将棋子移动到棋盘外，也不能将棋子移动到已有棋子的格子上。

由 ChatGPT 4.1 翻译