/ Vijos / 题库 /

兔兔和蛋蛋

兔兔和蛋蛋

描述

这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。
这个游戏是在一个 n 行 m 列的棋盘上进行的。游戏开始之前,棋盘上有一
个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。
每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为:
兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。
蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。
第一个不能按照规则操作的人输掉游戏。
img
img
img
最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——
你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中
所有她“犯错误”的地方。
注意:
两个格子相邻当且仅当它们有一条公共边。
兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,
而这次操作后蛋蛋有必胜策略。

格式

输入格式

输入的第一行包含两个正整数 n、m。
接下来 n行描述初始棋盘。其中第i 行包含 m个字符,每个字符都是大写英
文字母"X"、大写英文字母"O"或点号"."之一,分别表示对应的棋盘格中有黑色
棋子、有白色棋子和没有棋子。其中点号"."恰好出现一次。
接下来一行包含一个整数 k(1≤k≤1000) ,表示兔兔和蛋蛋各进行了k次操
作。
接下来 2k行描述一局游戏的过程。其中第 2i – 1行是兔兔的第 i 次操作(编
号为i的操作) ,第2i行是蛋蛋的第i次操作。每个操作使用两个整数x,y来描述,
表示将第x行第y列中的棋子移进空格中。
输入保证整个棋盘中只有一个格子没有棋子, 游戏过程中兔兔和蛋蛋的每个
操作都是合法的,且最后蛋蛋获胜。

输出格式

输出文件的第一行包含一个整数r,表示兔兔犯错误的总次数。
接下来r 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 i 行包含
一个整数ai表示兔兔第i 个犯错误的操作是他在游戏中的第 ai次操作。

样例1

样例输入1

1 6 
XO.OXO 
1 
1 2 
1 1 

样例输出1

1 
1 

样例2

样例输入2

3 3 
XOX 
O.O 
XOX 
4 
2 3 
1 3 
1 2 
1 1 
2 1 
3 1 
3 2 
3 3 

样例输出2

0

样例3

样例输入3

4 4 
OOXX 
OXXO 
OO.O 
XXXO 
2 
3 2 
2 2 
1 2 
1 3 

样例输出3

2 
1 
2 

限制

每个测试点1s

提示

1~2: n=1, 1<=m<=20
3: n=3, m=4
4~5: n=4, m=4
6~7: n=4, m=5
8: n=3, m=7
9~14: n=2, 1<=m<=40
15~16: 1<=n<=16, 1<=m<=16
17~20: 1<=n<=40, 1<=m<=40

来源

NOI 2011 DAY2 兔兔和蛋蛋的游戏

信息

ID
1718
难度
4
分类
博弈论 | 图结构 | 二分图匹配 点击显示
标签
递交数
87
已通过
40
通过率
46%
上传者

相关

在下列训练计划中:

RP++分类题库