#2005. 不围棋

不围棋

题目描述

小 F 对不围棋特别感兴趣,不过他经常输,所以他想做出一个 AI 来替他完成这局游戏。

不过造 AI 实在是太困难啦,小 F 千辛万苦写出来的 AI 被同学们的 AI 锤爆啦!

现在,他想请你帮他实现一个 AI 中一部分的功能——随机模拟,因为他相信你写的程序非常优秀,一定能优化他的 AI。

给你一个 n×nn \times n 的棋盘,上面或许已经有一些棋子了,但此时局面一定是合法的,即不存在没有气的连通块;此时轮到黑棋下棋,因此棋盘上黑白棋子的数量一定是相等的。

你的任务是,依次为黑棋和白棋随意指定一个可行的走子位置,直到某一步游戏无法进行,决出胜负为止。

在正式的不围棋比赛还存在一些禁手规则。不过由于小 F 玩的是一种棋盘大小可变的新型不围棋,我们只用考虑上面提到的气的规则就好。

输入格式

输入一行一个整数 nn,表示棋盘大小。 输入接下来 nn 行,每行有一个长度为 nn 的字符串,表示第 ii 行的情况。

  • . 表示空
  • X 表示黑棋
  • O 表示白棋

详细请参考样例。

输入保证,棋盘初始局面合法,X 与 O 数量相等。

输出格式

你需要输出至少一行,假设你输出了 LL 行,那么对于前 L−1L - 1 行,你应该输出两个用空格分隔的正整数表示下棋坐标 xi,yix_i, y_i,其中奇数行表示黑棋的行动,偶数行表示白棋的行动。xx 坐标为从上到下从 11 到 nn,yy 坐标为从左到右从 11 到 nn。

请在第 LL 行输出 -1 -1,表示此时第 LL 手执棋人已经无棋可走。

你的输出可能会很大,即使本题时限为 3s3s,也请你不要使用太慢的方法输出大量内容。

评分方式:

本题启用 Special Judge,并且有部分分。我们将通过以下方式进行计分:

  • 如果你输出格式错误,那么该测试点不得分。格式错误包括但不限于:输出了非数字内容;一行输出了超过或者少于两个正整数;输出的坐标在棋盘外;最后一行的输出不是 -1 -1。
  • 如果你的输出格式正确,但是你的输出的第一行的答案就是不可接受的,那么该测试点不得分。例如:输出的坐标是黑棋不可以下的位置;黑棋有棋可走却输出了 -1 -1。
  • 如果你的输出格式正确,并且你的前 $k(1 \leq k

    样例

3
XXX
OOX
OO.
-1 -1
3
XOO
XO.
X..
2 3
-1 -1

题目来源:洛谷 P4997