#P1971. [NOI2011] 兔兔与蛋蛋游戏

    ID: 994 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2011最大匹配NOI 系列深度优先搜索DFS二分图

[NOI2011] 兔兔与蛋蛋游戏

题目描述

这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。

这个游戏是在一个 nnmm 列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。

每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为:

  • 兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。
  • 蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。

第一个不能按照规则操作的人输掉游戏。为了描述方便,下面将操作“将第x行第y列中的棋子移进空格中”记为 M(x,y)M(x,y)

例如下面是三个游戏的例子。

最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中所有她“犯错误”的地方。

注意:

  • 两个格子相邻当且仅当它们有一条公共边。
  • 兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,而这次操作后蛋蛋有必胜策略。

输入格式

输入的第一行包含两个正整数 n,mn,m

接下来 nn 行描述初始棋盘。其中第 ii 行包含 mm 个字符,每个字符都是大写英文字母 X、大写英文字母 O 或点号 . 之一,分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号 . 恰好出现一次。

接下来一行包含一个整数 kk1k10001\leq k\leq 1000) ,表示兔兔和蛋蛋各进行了 kk 次操作。

接下来 2k2k 行描述一局游戏的过程。其中第 2i12i - 1 行是兔兔的第 ii 次操作(编号为 ii 的操作) ,第 2i2i 行是蛋蛋的第 ii 次操作。每个操作使用两个整数 x,yx,y 来描述,表示将第 xx 行第 yy 列中的棋子移进空格中。

输入保证整个棋盘中只有一个格子没有棋子, 游戏过程中兔兔和蛋蛋的每个操作都是合法的,且最后蛋蛋获胜。

输出格式

输出文件的第一行包含一个整数 rr,表示兔兔犯错误的总次数。

接下来 rr 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 ii 行包含一个整数 aia_i 表示兔兔第 ii 个犯错误的操作是他在游戏中的第 aia_i 次操作。

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

提示

对于 100%100\% 的数据,1n401\leq n\leq 401m401 \leq m\leq 401k10001\leq k\leq 1000

测试点编号 nn mm
1,21,2 n=1n=1 1m201\leq m\leq 20
33 n=3n=3 m=4m=4
4,54,5 n=4n=4
6,76,7 m=5m=5
88 n=3n=3 m=7m=7
9149\sim 14 n=2n=2 1m401\leq m\leq 40
15,1615,16 1n161\leq n\leq 16 1m161\leq m\leq 16
172017\sim 20 1n401\leq n\leq 40 1m401\leq m\leq 40