#2447. 「NOI2011」兔兔与蛋蛋的游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

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

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

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

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

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

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

注意:

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

输入格式

输入的第一行包含两个正整数 nnnmmm

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

接下来一行包含一个整数 kkk1≤k≤10001 \le k \le 10001k1000),表示兔兔和蛋蛋各进行了 kkk 次操作。

接下来 2k2k2k 行描述一局游戏的过程。其中第 2i1 行是兔兔的第 iii 次操作(编号为 iii 的操作),第 2i2i2i 行是蛋蛋的第 iii 次操作。每个操作使用两个整数 x,yx,yx,y 来描述,表示将第 xxx 行第 yyy 列中的棋子移进空格中。

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

输出格式

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

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

样例

样例输入 1

1 6
XO.OXO
1
1 2
1 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

样例解释

样例 1 对应图一中的游戏过程。 样例 2 对应图三中的游戏过程。

数据范围与提示

测试点编号 nnn 的规模 mmm 的规模
1 n=1n = 1n=1 1≤m≤201 \le m \le 201m20
2 n=1n = 1n=1 1≤m≤201 \le m \le 201m20
3 n=3n = 3n=3 m=4m = 4m=4
4 n=4n = 4n=4 m=4m = 4m=4
5 n=4n = 4n=4 m=4m = 4m=4
6 n=4n = 4n=4 m=5m = 5m=5
7 n=4n = 4n=4 m=5m = 5m=5
8 n=3n = 3n=3 m=7m = 7m=7
9 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
10 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
11 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
12 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
13 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
14 n=2n = 2n=2 1≤m≤401 \le m \le 401m40
15 1≤n≤161 \le n \le 161n16 1≤m≤161 \le m \le 161m16
16 1≤n≤161 \le n \le 161n16 1≤m≤161 \le m \le 161m16
17 1≤n≤401 \le n \le 401n40 1≤m≤401 \le m \le 401m40
18 1≤n≤401 \le n \le 401n40 1≤m≤401 \le m \le 401m40
19 1≤n≤401 \le n \le 401n40 1≤m≤401 \le m \le 401m40
20 1≤n≤401 \le n \le 401n40 1≤m≤401 \le m \le 401m40