← 返回题目列表

AtCoder · abc201_d

D. 桃色世界的游戏

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个网格 H 行和 W 方格列,其中每个方格都是蓝色或红色。广场位于 i第行和 j- 第列为蓝色,如果 A_{i, j} is +,如果 A_{i, j} is -.
该网格上有一个棋子,最初放置在左上角的方块上。高桥和青木将用这件作品玩一个游戏。
两名玩家各有 0 点在开头。他们将交替进行以下操作,高桥首先进行:

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

当其中一名玩家无法执行操作时,游戏结束。然后,如果分数不同,则分数较高的玩家获胜。否则,比赛平局。
求双方玩游戏时获得最佳结果时的游戏结果。

约束

  • 1 \le H, W \le 2000
  • A_{i, j} is + or -.

输入

输入由标准输入按以下格式给出:

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 获胜,则打印 Aoki;如果比赛是平局,则打印 Draw.


示例输入 1

3 3
---
+-+
+--

示例输出 1

Takahashi

高桥有如下获胜策略。

首先,高桥将棋子向右移动,这使他失去一分,因为棋子进入了红色方块。现在,高桥已经 -1 点和青木有 0 点。然后,

  • 如果青木将棋子向右移动,高桥将其向下移动;
  • 如果青木将棋子向下移动,高桥将其向右移动。

无论哪种情况,青木将棋子移动到红色方格都会失去一分,而高桥将棋子移动到蓝色方格会得到一分,这意味着现在高桥有 0 分和青木有 -1 点。
该棋子现在位于广场上 2- 从顶部开始的第 1 行和 3- 从左边算起第 3 列,青木只能选择将其向下移动到红色方块。现在,高桥已经 0 分和青木有 -2 点。
该棋子无法再向右或向下移动,因此游戏结束。由于高桥得分较多,因此他获胜。


示例输入 2

2 4
+++-
-+-+

示例输出 2

Aoki

无论高桥做出什么选择,青木都能赢得比赛。


示例输入 3

1 1
-

示例输出 3

Draw

在这种情况下,游戏立即结束。由于双方球员都有 0 分,比赛平局。