DMPG '19 G4 - Carpet Cleaning Chore

View as PDF

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

Bob is doing some spring cleaning! He has a rectangular carpet which can be represented as an by grid of cells. Each cell is either dirty or clean. Bob can clean this grid by choosing a subrectangle which contains the top-left cell (in row , column ), and reversing the states of all the cells in this subrectangle. This constitutes a single move. He wants to clean the carpet in as few moves as possible. In addition, the carpet changes sometimes. There are changes to the carpet of the form in which the cell in row , column becomes reversed. After each change, can you tell Bob the minimum number of moves he needs to make his carpet pristine?

Input Specification

The first line contains two space-separated integers, and .
The next lines each contain a string of characters, either C or D which represents a clean or dirty cell respectively.
The following line contains a single integer, .
The next lines each contain two space-separated integers, and .

Output Specification

Output lines. Each line should contain a single integer, the answer after each change.

Sample Input 1

3 4
CCCC
CCCC
CCCC
3
1 1
2 1
1 2

Sample Output 1

1
1
3

Explanation for Sample 1

The carpet after each change is:

DCCC    DCCC    DDCC
CCCC    DCCC    DCCC
CCCC    CCCC    CCCC

Then to clean the third carpet, for example, Bob first chooses the subrectangle from (1, 2):

CCCC
DCCC
CCCC

Next he chooses the subrectangle from (2, 1):

DCCC
CCCC
CCCC

Finally, he chooses the subrectangle from (1, 1):

CCCC
CCCC
CCCC

which gives three moves.

Sample Input 2

3 3
CCC
CDC
CCC
3
2 1
2 1
2 2

Sample Output 2

2
4
0