← 返回题目列表

AtCoder · arc002_4

D. 棋盘游戏

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

問題文

高桥对于在格斗游戏中输给朋友感到很难过,因此他建议了一个他可以获胜的游戏。
提议的游戏包括面对面坐在由网格状方块组成的棋盘上。 1 与 ○ 列的位置,最右侧 1 该列将位于 × 位置。
使用随机排列的○和×片,2 每个人选择○或×作为他们的棋子。
图:电路板示例。最左边的红色列是○位置,最右边的蓝色列是×位置。
棋子向对手的基地移动。1 一次向前移动一格,将对手踩到的棋子从棋盘上移走。 你只能向
前 1方向移动;你不能沿对角线、侧向或向后移动。
另外,你不能踩到自己的棋子。

交替 1 将你的棋子一颗一颗地移动,移除对手的所有棋子,或者将你的棋子移动到对手的基地。 1 如果你放置了任何一个,你就赢了。
第一个玩家是拥有带有圆圈的棋子的玩家。 1 最初的安排是不可能在卷上打×。
此外,初始位置尚未满足任一胜利条件。

高桥想要赢,所以他很难在○和×之间做出选择。
决定○或×获胜,以便高桥获胜。

入力

输入将以以下格式从标准输入给出。
H W
c_{11}c_{12}…c_{1W} 
c_{21}c_{22}…c_{2W}
:
:
c_{H1}c_{H2}…c_{HW}
  • 1 行是一个整数,表示棋盘的高度。 H (1 ≦ H ≦ 2,000), 代表棋盘宽度的整数 W (3 ≦ W ≦ 2,000) 作为空格分隔符给出。 来自行
  • 2 从行 H 行代表棋盘上棋子的放置位置。 W 给出一个字符串。
  • i 从行首开始 是第 j 个字符 c_{ij}是 如果., o, x。 在
  • c_{ij} 是 作者: . 的情况下,没有放置任何棋子。o ○ 件是x 表示放置了×棋子。

出力

如果○获胜o,如果 × 获胜,则x 到标准输出 1 按行输出。
请在末尾输出换行符。

入力例 1

3 10
..o.o.xxx.
...o.xo.x.
o.xxo..x..

出力例 1

o
  • 首先,前面的○是 3 从左起行 将第 5 块移到右侧。
  • 现在轮到X了,但是无论你能向左移动哪个棋子,它都会被下一个O棋子吃掉。
  • 被吃掉后,和以前一样,无论你移动哪一个棋子,前进到下一圈的棋子都会被吃掉(只能移动到图中浅蓝色框处)。
  • 即第一个 1 手工 通过将第 3 从左起行 将第 5 棋子向右移动,○的胜利就确定了。

入力例 2

3 5
..x..
.o...
...x.

出力例 2

x
  • 不要互相踩踏,○是最短的 3 手,× 是 2 你可以用手到达对手的基地,所以你赢了。