← 返回题目列表

AtCoder · xmascon18_g

G. 好游戏

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

配点 : 100 点

黑兔子「交替放置棋子」

白兔子「是游戏吗?」

黑兔子「自己的颜色棋子 2 \times 2 不可以形成块」

白兔子「完全理解了」

黑兔子「轮到谁下由你选择」

問題文

黑兔子和白兔子打算进行如下游戏。

  • H 行 W 在列的格子中,黑兔子放黑石,白兔子放白石。
  • 最初,白兔选择先手还是后手,然后交替 1 每次放置一个棋子。
  • 已经有棋子的格子不能再放置棋子。
  • 自己颜色的棋子不能形成 2 \times 2 块状。也就是说,不能出现某个格点被 4 所有相邻的格子都放上自己的棋子的情况。
  • 先下子的人输。

请制作一个程序,来替代去玩这个游戏并获胜。

游戏是 T 连续进行多次,所以必须全部获胜。

制約

  • 1 \leq T \leq 25
  • 1 \leq H,W \leq 40

部分点

  • H, W 如果对所有两个都为偶数的测试用例都答对,25 点。 如果所有满足
  • 如果对所有测试用例都答对,则除此之外 75 点。 如果所有满足

入出力

  1. 整数 T 将通过标准输入提供。
  2. 以下内容将被 T 次重复。
    1. 整数 H, W 会以空格分隔形式提供给标准输入。
    2. 你的程序必须 First 或 至少 Second 并输出,这分别表示选择先手或后手。
    3. 在胜负未定之前重复以下操作。
      • 自己的回合时:2 整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) 以空格分隔形式输出。这表示 r 行目 c 在第列格子上放置白棋。
      • 对方回合时:2 整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) 会以空格分隔形式提供给标准输入。这表示 r 行目 c 在第列格子上放置了黑棋。但是,如果没有可以放置黑棋的格子, -1 -1 将会提供给标准输入。在这种情况下,白兔获胜,游戏结束。

也请参考输入输出示例。

注意点

T 回合的游戏结束后,你的程序必须立即终止。 如果没有终止,评判结果将不确定。 另外,如果输出不正确,结果也不确定(不一定会 WA 这样)。

如果你的程序在赢得所有游戏后终止,则视为正确答案。

注意,在输出后必须刷新输出。如果不刷新输出,可能会导致 TLE。

每种语言的输入/输出方法都是过去 AtCoder 问题中提出的问题(链接: ABC 019 D:高桥君和树的直径) 参考就好。

入出力例

入力 出力 説明
2 T 已经被给出。
2 1 H, W 已经被给出。
第二 选择了后手。
1 0 黑兔在 1,0 放置了黑子。
0 0 白兔在 0,0 放置了白子。
-1 -1 表示没有可以放置黑石的格子。
1 1 H, W 已经被给出。
第一 选择了先手。
0 0 白兔在 0,0 放置了白子。
-1 -1 表示没有可以放置黑石的格子。