a376: NOI2011 Day2.3.兔兔与蛋蛋游戏
Tags :
Accepted rate : 12人/12人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 01:23

Content
这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。 这个游戏是在一个n行m列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。 每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为:
 兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。
 蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。
第一个不能按照规则操作的人输掉游戏。为了描述方便,下面将操作“将第x行第y列中的棋子移进空格中”记为M(x,y)。 例如下面是三个游戏的例子。

图1

图2


图3

最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中所有她“犯错误”的地方。 注意:
 两个格子相邻当且仅当它们有一条公共边。
 兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,而这次操作后蛋蛋有必胜策略。

Input

输入的第一行包含两个正整数n、m。

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

接下来一行包含一个整数k(1≤k≤1000),表示兔兔和蛋蛋各进行了k次操作。

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

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

Output

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

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

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

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

0

2
1
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
【样例说明】
样例1对应图一中的游戏过程。
样例2对应图三中的游戏过程。

【数据规模】
所有测试数据的范围和特点如下表所示

测试点编号

n的规模m的规模
1n = 11 m 20
2
3n = 3m = 4
4n = 4m = 4
5
6n = 4m = 5
7
8n = 3m = 7
9n = 21 m 40
10
11
12
13
14
151 n 161 m 16
16
171 n 401 m 40
18
19
20
Tags:
出處:
NOI2011Day2第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」