4454: 「NOI2011」兔兔与蛋蛋的游戏
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。
这个游戏是在一个 $n$ 行 $m$ 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。
每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：
* 兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。
* 蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。
第一个不能按照规则操作的人输掉游戏。为了描述方便，下面将操作“将第 $x$ 行第 $y$ 列中的棋子移进空格中”记为 $M(x,y)$。
例如下面是三个游戏的例子。
最近兔兔总是输掉游戏，而且蛋蛋格外嚣张，于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录，请你指出这一局游戏中所有她“犯错误”的地方。
注意：
* 两个格子相邻当且仅当它们有一条公共边。
* 兔兔的操作是“犯错误”的，当且仅当，在这次操作前兔兔有必胜策略，而这次操作后蛋蛋有必胜策略。
输入
输入的第一行包含两个正整数 $n$、$m$。
接下来 $n$ 行描述初始棋盘。其中第 $i$ 行包含 $m$ 个字符，每个字符都是大写英文字母 `X`、大写英文字母 `O` 或点号 `.` 之一，分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号 `.` 恰好出现一次。
接下来一行包含一个整数 $k$（$1 \le k \le 1000$），表示兔兔和蛋蛋各进行了 $k$ 次操作。
接下来 $2k$ 行描述一局游戏的过程。其中第 $2i – 1$ 行是兔兔的第 $i$ 次操作（编号为 $i$ 的操作），第 $2i$ 行是蛋蛋的第 $i$ 次操作。每个操作使用两个整数 $x,y$ 来描述，表示将第 $x$ 行第 $y$ 列中的棋子移进空格中。
输入保证整个棋盘中只有一个格子没有棋子，游戏过程中兔兔和蛋蛋的每个操作都是合法的，且最后蛋蛋获胜。
输出
输出文件的第一行包含一个整数 $r$，表示兔兔犯错误的总次数。
接下来 $r$ 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 $i$ 行包含一个整数 $a_i$ 表示兔兔第 $i$ 个犯错误的操作是他在游戏中的第 $a_i$ 次操作。
样例输入 复制
1 6
XO.OXO
1
1 2
1 1样例输出 复制
1
1提示
输入样例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
4 4 OOXX OXXO OO.O XXXO 2 3 2 2 2 1 2 1 3
输出样例3
2 1 2
数据范围：| 测试点编号 | $n$ 的规模 | $m$ 的规模 | | :-: | :-: | :-: | | 1 | $n = 1$ | $1 \le m \le 20$ | | 2 | $n = 1$ | $1 \le m \le 20$ | | 3 | $n = 3$ | $m = 4$ | | 4 | $n = 4$ | $m = 4$ | | 5 | $n = 4$ | $m = 4$ | | 6 | $n = 4$ | $m = 5$ | | 7 | $n = 4$ | $m = 5$ | | 8 | $n = 3$ | $m = 7$ | | 9 | $n = 2$ | $1 \le m \le 40$ | | 10 | $n = 2$ | $1 \le m \le 40$ | | 11 | $n = 2$ | $1 \le m \le 40$ | | 12 | $n = 2$ | $1 \le m \le 40$ | | 13 | $n = 2$ | $1 \le m \le 40$ | | 14 | $n = 2$ | $1 \le m \le 40$ | | 15 | $1 \le n \le 16$ | $1 \le m \le 16$ | | 16 | $1 \le n \le 16$ | $1 \le m \le 16$ | | 17 | $1 \le n \le 40$ | $1 \le m \le 40$ | | 18 | $1 \le n \le 40$ | $1 \le m \le 40$ | | 19 | $1 \le n \le 40$ | $1 \le m \le 40$ | | 20 | $1 \le n \le 40$ | $1 \le m \le 40$ |