D - 菠萝睡眠世界的游戏

得分：400分

题目描述

我们有一个 $H$ 行 $W$ 列的方块网格，每个方块要么是蓝色，要么是红色。第 $i$ 行第 $j$ 列的方块是蓝色当且仅当 $A_{i, j}$ 是 +，是红色当且仅当 $A_{i, j}$ 是 -。
这个网格上有一块棋子，初始时位于左上角方块上。小高和小明要使用这块棋子进行游戏。
两个玩家轮流进行以下操作，小高先开始：

• 将棋子向右移动一格或向下移动一格。不允许移出网格。如果棋子现在位于蓝色方块上，移动棋子的玩家得到 1 分；如果棋子现在位于红色方块上，移动棋子的玩家失去 1 分。

当其中一个玩家无法进行操作时，游戏结束。此时，如果两位玩家的分数不相等，拥有更高分数的玩家获胜。如果两位玩家的分数相等，游戏平局。
请计算当两位玩家都采取最优策略进行游戏时的最终结果。

约束

• $1 \le H, W \le 2000$
• $A_{i, j}$ 是 + 或 -。

输入

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

$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。

3 3
---
+-+
+--

Takahashi

小高的获胜策略如下：

首先，小高将棋子向右移动一格，这使他失去一分，因为棋子进入了一个红色方块。现在，小高得分为 $-1$，小明得分为 $0$。接着，

• 如果小明将棋子向右移动，小高将其向下移动；
• 如果小明将棋子向下移动，小高将其向右移动。

无论哪种情况，小明将棋子移到一个红色方块上失去一分，小高将棋子移到一个蓝色方块上得到一分，这意味着现在小高的得分为 $0$，小明的得分为 $-1$。
棋子现在位于网格的第 $2$ 行第 $3$ 列的方块上，小明只能选择向下移动棋子，使其进入红色方块。现在，小高得分为 $0$，小明得分为 $-2$。
棋子不能再向右或向下移动，所以游戏结束。由于小高的得分更高，他获胜。

2 4
+++-
-+-+

Aoki

无论小高做出什么选择，小明都能赢得游戏。

1 1
-

Draw

在这种情况下，游戏立即结束。由于两位玩家的得分都是 $0$，游戏平局。