102297: [AtCoder]ABC229 H - Advance or Eat
Description
Score : $600$ points
Problem Statement
There is a grid with $N$ rows and $N$ columns, where each square has one white piece, one black piece, or nothing on it.
The square at the $i$-th row from the top and $j$-th column from the left is described by $S_{i,j}$. If $S_{i,j}$ is W
, the square has a white piece; if $S_{i,j}$ is B
, it has a black piece; if $S_{i,j}$ is .
, it is empty.
Takahashi and Snuke will play a game, where the players take alternate turns, with Takahashi going first.
In Takahashi's turn, he does one of the following operations.
- Choose a white piece that can move one square up to an empty square, and move it one square up (see below).
- Eat a black piece of his choice.
In Snuke's turn, he does one of the following operations.
- Choose a black piece that can move one square up to an empty square, and move it one square up.
- Eat a white piece of his choice.
The player who becomes unable to do the operation loses the game. Which player will win when both players play optimally?
Here, moving a piece one square up means moving a piece at the $i$-th row and $j$-th column to the $(i-1)$-th row and $j$-th column.
Note that this is the same for both players; they see the board from the same direction.
Constraints
- $1 \leq N \leq 8$
- $N$ is an integer.
- $S_{i,j}$ is
W
,B
, or.
.
Input
Input is given from Standard Input in the following format:
$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}$
Output
If Takahashi will win, print Takahashi
; if Snuke will win, print Snuke
.
Sample Input 1
3 BB. .B. ...
Sample Output 1
Takahashi
If Takahashi eats the black piece at the $1$-st row and $1$-st columns, the board will become:
.B. .B. ...
Then, Snuke cannot do an operation, making Takahashi win.
Note that it is forbidden to move a piece out of the board or to a square occupied by another piece.
Sample Input 2
2 .. WW
Sample Output 2
Snuke
Sample Input 3
4 WWBW WWWW BWB. BBBB
Sample Output 3
Snuke
Input
题意翻译
给定一个 $n\times n$ 的棋盘, 每个格子上有一个黑棋或一个白棋或什么也没有, 两人轮流进行操作, 无法进行操作的人输. 先手每次可以进行以下两种操作之一 1. 选一个可以向上移动的白棋, 将其上移一格. 2. 吃掉一个黑棋. 后手每次可以进行以下两种操作之一 1. 选一个可以向上移动的黑棋, 将其上移一格. 2. 吃掉一个白棋. 不能将棋子移出棋盘. 加入两人均走最优策略, 问最终胜者是谁. (两人看棋盘的方向相同)Output
得分:600分
问题描述
有一个包含$N$行和$N$列的网格,每个方块上有一个白色棋子、一个黑色棋子或什么都没有。
从顶部数第$i$行,从左数第$j$列的方块由$S_{i,j}$描述。如果$S_{i,j}$是W
,则该方块上有一个白色棋子;如果$S_{i,j}$是B
,则该方块上有一个黑色棋子;如果$S_{i,j}$是.
,则该方块为空。
高桥和スネーク将进行一场比赛,玩家轮流行动,高桥先走。
在高桥的回合中,他会执行以下操作之一。
- 选择一个可以向上移动一个空格的白色棋子,并将其向上移动一个空格(见下文)。
- 吃掉一个他选择的黑色棋子。
在スネーク的回合中,他会执行以下操作之一。
- 选择一个可以向上移动一个空格的黑色棋子,并将其向上移动一个空格。
- 吃掉一个他选择的白色棋子。
当玩家无法执行操作时,该玩家输掉比赛。当两个玩家都发挥出最佳水平时,哪位玩家会赢?
在这里,将棋子向上移动一个空格意味着将位于第$i$行和第$j$列的棋子移动到第$(i-1)$行和第$j$列。
请注意,对于双方来说都是如此;他们从同一个方向看棋盘。
限制条件
- $1 \leq N \leq 8$
- $N$是一个整数。
- $S_{i,j}$是
W
,B
或.
。
输入
输入将以以下格式从标准输入给出:
$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
3
BB.
.B.
...
样例输出 1
Takahashi
如果高桥吃掉位于第$1$行和第$1$列的黑色棋子,棋盘将变为:
.B.
.B.
...
然后,スネーク无法执行操作,使高桥获胜。
请注意,禁止将棋子移出棋盘或移至另一个棋子所在的方块。
样例输入 2
2
..
WW
样例输出 2
Snuke
样例输入 3
4
WWBW
WWWW
BWB.
BBBB
样例输出 3
Snuke