#P1971. [NOI2011] 兔兔与蛋蛋游戏
[NOI2011] 兔兔与蛋蛋游戏
题目描述
这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。
这个游戏是在一个 行 列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。
每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为:
- 兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。
- 蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。
第一个不能按照规则操作的人输掉游戏。为了描述方便,下面将操作“将第x行第y列中的棋子移进空格中”记为 。
例如下面是三个游戏的例子。
最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中所有她“犯错误”的地方。
注意:
- 两个格子相邻当且仅当它们有一条公共边。
- 兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,而这次操作后蛋蛋有必胜策略。
输入格式
输入的第一行包含两个正整数 。
接下来 行描述初始棋盘。其中第 行包含 个字符,每个字符都是大写英文字母 X
、大写英文字母 O
或点号 .
之一,分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号 .
恰好出现一次。
接下来一行包含一个整数 () ,表示兔兔和蛋蛋各进行了 次操作。
接下来 行描述一局游戏的过程。其中第 行是兔兔的第 次操作(编号为 的操作) ,第 行是蛋蛋的第 次操作。每个操作使用两个整数 来描述,表示将第 行第 列中的棋子移进空格中。
输入保证整个棋盘中只有一个格子没有棋子, 游戏过程中兔兔和蛋蛋的每个操作都是合法的,且最后蛋蛋获胜。
输出格式
输出文件的第一行包含一个整数 ,表示兔兔犯错误的总次数。
接下来 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 行包含一个整数 表示兔兔第 个犯错误的操作是他在游戏中的第 次操作。
1 6
XO.OXO
1
1 2
1 1
1
1
3 3
XOX
O.O
XOX
4
2 3
1 3
1 2
1 1
2 1
3 1
3 2
3 3
0
4 4
OOXX
OXXO
OO.O
XXXO
2
3 2
2 2
1 2
1 3
2
1
2
提示
对于 的数据,,,。
测试点编号 | ||
---|---|---|