DMPG '19 G4 - Carpet Cleaning Chore

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Bob is doing some spring cleaning! He has a rectangular carpet which can be represented as an M by N 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 1, column 1), 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 Q changes to the carpet of the form a_i\ b_i in which the cell in row a_i, column b_i becomes reversed. After each change, can you tell Bob the minimum number of moves he needs to make his carpet pristine?

Constraints

1 \le a_i \le M
1 \le b_i \le N

Subtask 1 [20%]

1 \le M, N \le 1\,000
Q = 1

Subtask 2 [20%]

M = 1
1 \le N \le 1\,000
1 \le Q\le 500\,000

Subtask 3 [60%]

1 \le M, N \le 1\,000
1 \le Q \le 500\,000

Input Specification

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

Output Specification

Output Q 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

Comments

There are no comments at the moment.