AT_abc201_d [ABC201D] Game in Momotetsu World

题目描述

有一个 $H$ 行 $W$ 列的格子，每个格子要么是蓝色格子，要么是红色格子。第 $i$ 行第 $j$ 列的格子，如果 $A_{i,j}$ 为 +，则为蓝色格子；如果为 -，则为红色格子。 最初，有一个棋子放在格子的左上角，高桥君和青木君用这个棋子进行游戏。 两人的初始得分都是 $0$。两人轮流操作，从高桥君开始，每次可以进行以下操作：

• 将棋子向右或向下移动一格，但不能将棋子移出格子范围。移动后，如果棋子所在格子是蓝色格子，则操作者得 $1$ 分；如果是红色格子，则失去 $1$ 分。

当某一方无法再操作时，游戏结束。若两人的得分不同，则得分高者获胜；若得分相同，则为平局。 假设双方都采取最优策略，请你输出游戏的结果。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$
$A_{1,1}A_{1,2}A_{1,3}\dots A_{1,W}$
$A_{2,1}A_{2,2}A_{2,3}\dots A_{2,W}$
$A_{3,1}A_{3,2}A_{3,3}\dots A_{3,W}$
$\hspace{2cm}\vdots$
$A_{H,1}A_{H,2}A_{H,3}\dots A_{H,W}$

输出格式

如果高桥君获胜，输出 Takahashi；如果青木君获胜，输出 Aoki；如果平局，输出 Draw。

输入输出样例 #1

输入 #1

3 3
---
+-+
+--

输出 #1

Takahashi

输入输出样例 #2

输入 #2

2 4
+++-
-+-+

输出 #2

Aoki

输入输出样例 #3

输入 #3

1 1
-

输出 #3

Draw

说明/提示

限制条件

• $1 \leq H, W \leq 2000$
• $A_{i,j}$ 仅为 + 或 -

样例解释 1

高桥君可以通过如下策略获胜。首先高桥君将棋子向右移动。移动后的格子为红色格子，因此高桥君失去 $1$ 分，当前得分分别为 $-1, 0$。

• 如果青木君接下来向右移动，则高桥君向下移动；
• 如果青木君向下移动，则高桥君向右移动。 无论哪种情况，青木君都会将棋子移动到红色格子，失去 $1$ 分，而高桥君会移动到蓝色格子，获得 $1$ 分，因此得分分别为 $0, -1$。 此时棋子在第 $2$ 行第 $3$ 列，下一步青木君只能向下移动，移动到红色格子，得分分别为 $0, -2$。 此时棋子无法再移动，游戏结束，高桥君获胜。

样例解释 2

无论高桥君如何操作，青木君都能通过最优策略获胜。

样例解释 3

此时游戏立即结束，双方得分均为 $0$，结果为平局。

由 ChatGPT 4.1 翻译