Game in Momotetsu World

题目描述

我们有一个由 $H$ 行 $W$ 列方格组成的网格，每个方格是蓝色或红色。位于第 $i$ 行第 $j$ 列的方格当且仅当 $A_{i, j}$ 为 $+$ 时为蓝色，若为 $-$ 则为红色。
网格上有一枚棋子，初始放在左上角的方格。Takahashi 和 Aoki 将使用这枚棋子进行一个游戏。
两位玩家开始时的得分均为 $0$。他们将交替执行以下操作，Takahashi 先手：

将棋子向右移动一个格或向下移动一个格。不允许将棋子移出网格。然后，移动棋子的玩家若此时棋子位于蓝色方格则得一分，若位于红色方格则失一分。

当某一位玩家无法执行该操作时游戏结束。若两位玩家的分数不同，则分数更高的一方获胜；否则，游戏判为平局。
在双方都采取最优策略的情况下，求该游戏的结果。

输入格式

输入从标准输入给出，格式如下： $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 将获胜，输出 $Takahashi$；若 Aoki 将获胜，输出 $Aoki$；若游戏将平局，输出 $Draw$。

3 3
---
+-+
+--

Takahashi

2 4
+++-
-+-+

Aoki

1 1
-

Draw

提示

$1 \le H, W \le 2000$ $A_{i, j}$ 为 $+$ 或 $-$。Takahashi 有如下的制胜策略。 首先，Takahashi 将棋子向右移动，这使得他因为棋子进入红色方格而失一分。现在，Takahashi 的得分为 $-1$，Aoki 的得分为 $0$。然后，

如果 Aoki 将棋子向右移动，Takahashi 将棋子向下移动； 如果 Aoki 将棋子向下移动，Takahashi 将棋子向右移动。

无论哪种情况，Aoki 都会把棋子移到一个红色方格从而失一分，而 Takahashi 会把棋子移到一个蓝色方格从而得一分，这意味着现在 Takahashi 的得分为 $0$ 而 Aoki 的得分为 $-1$。
此时棋子位于自上向下第 $2$ 行、自左向右第 $3$ 列的方格，Aoki 只能选择向下移动到一个红色方格。现在，Takahashi 的得分为 $0$ 而 Aoki 的得分为 $-2$。
此时无法再向右或向下移动棋子，游戏结束。由于 Takahashi 的得分更高，他获胜。
Aoki 可以获胜，无论 Takahashi 做何选择。
在这种情况下，游戏会立即结束。由于双方得分均为 $0$，比赛判为平局。

标签: AtCoder|abc201D

来源

AtCoder|abc201D