H - Advance or Eat Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 行 N 列のグリッドがあり、各マスには白い駒が 1 個置かれているか、黒い駒が 1 個置かれているか、何も置かれていないかのいずれかです。
上から i 行目、左から j 列目のマスの状態は S_{i,j} で表され、W のとき白い駒が置かれていて、B のとき黒い駒が置かれていて、. のときは何も置かれていない空マスです。

高橋君とすぬけ君がゲームをします。高橋君からはじめて、交互にターンが回ってきます。

高橋君のターンには、

  • 1 つ上に空マスがあるような白い駒を 1 つ選び、上に進める
  • 好きな黒い駒を 1 つ食べる

のいずれかの操作をします。

すぬけ君のターンには、

  • 1 つ上に空マスがあるような黒い駒を 1 つ選び、上に進める
  • 好きな白い駒を 1 つ食べる

のいずれかの操作をします。

操作ができなくなった方が負けとします。両者が最適に行動するとき、どちらが勝ちますか？

なお「駒を上に進める」とは、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

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