National Olympiad in Informatics, China, 2011

Day 2, Problem 3 - Bunny and Eggy's Game

Recently, Bunny and Eggy have developed an interest in a new type of board game.

This game is played on an n rows tall by m columns wide board. Once the game starts, the board will contain a single square that is empty. All other squares will contain a single piece that's either black or white.

Each game will always have Bunny go first, followed by them alternating. The general steps are:

• Every time Bunny moves, she will select a white piece adjacent to the empty square and move it onto the space.
• Every time Eggy moves, he will select a black piece adjacent to the empty square and move it onto the space.

The first person that cannot follow the above loses the game. To simplify our description, we denote the action of "moving the piece from row x, column y to the empty space" as M(x, y). The following are three examples of entire games.

Figure 1

Figure 2

Figure 3

Bunny has been losing a lot recently, and thus Eggy has been getting overly arrogant. Bunny wants to invite her good friend – you! – to help her. She has brought over a game which she has lost to Eggy, and wishes for you to point out all of the "mistakes" she made.

Note:

• Two squares are considered adjacent if and only if they share an edge.
• A move of Bunny's is a "mistake" if and only if Bunny had a guaranteed winning strategy before it was made, and Eggy had a guaranteed winning strategy after it was made.

Input Format

The first line of input contains two positive integers n and m.
The following n lines will describe the game board. The i-th of these lines will contain m characters, where each character can either be an uppercase 'X', an uppercase 'O', or a period '.'. Respectively, they represent a black piece on a square, a white piece on a square, and an empty square. The '.' character will appear exactly once.
The following line contains a single integer k (1 ≤ k ≤ 1000), indicating that Bunny and Eggy each made k moves.
The following 2k lines will describe the process of a game. The (2i − 1)th of these lines will represent Bunny's i-th move, and the 2i-th of these lines will represent Eggy's i-th move. Each move will be described using two integers x and y, indicating that the piece in row x, column y will be moved onto the empty square.
The input guarantees that there will be exactly one empty square, all moves made by Bunny and Eggy in the process are valid, and that Eggy will be the winner at the end.

Output Format

The first line of output should contain a single integer r, representing the total number of times that Bunny has made a mistake.
The following r lines should give the actual move numbers of the mistakes in ascending order. The i-th of these lines should contain a single integer a_i, indicating the i-th mistake Bunny made is her a_i-th move in the game.

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

Explanation

Sample 1 corresponds to the example in figure 1.
Sample 2 corresponds to the example in figure 3.

Constraints

The attributes of all the test cases are outlined below.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Aug 10, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)