Problems
Farmer John has a square canvas represented by an N x N grid of cells (2 ≤ N ≤ 2000, N is even). He paints the canvas according to the following steps:
First, he divides the canvas into four equal quadrants, separated by horizontal and vertical lines through the center of the canvas.
Next, he paints a lovely painting in the top-right quadrant of the canvas. Each cell of the top-right quadrant will either be painted (represented by '#') or unpainted (represented by '.').
Finally, since he is so proud of his painting, he reflects it across the previously mentioned horizontal and vertical lines into the other quadrants of the canvas.
For example, suppose N = 8 and Farmer John painted the following painting in the top-right quadrant in step 2:
.#..
.#..
.##.
....
Then, after reflecting across the horizontal and vertical lines into the other quadrants in step 3, the canvas would look as follows:
..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..
However, while Farmer John was sleeping, Bessie broke into his barn and stole his precious canvas. She completely vandalized the canvas — removing some painted cells and adding more painted cells! Before Farmer John woke up, she returned the canvas to him.
Farmer John would like to modify his canvas so that it once again satisfies the reflective condition; that is, it becomes the result of reflecting the top-right quadrant into each of the other quadrants. Since he has a limited number of resources, he would like to achieve this in as few operations as possible, where a single operation consists of either painting a cell or removing paint from a cell.
You are given the canvas after Bessie's vandalism, as well as a sequence of U updates (0 ≤ U ≤ 10^5) to the canvas, each toggling a single cell to '.' if it is '#' or vice versa. Before any updates, and after each update, output the minimum number of operations that Farmer John needs to perform so that the reflective condition is satisfied.
Input
The first line contains the integers N and U.
The next N lines each contain N characters representing the canvas after Bessie's vandalism. Every character is either '#' or '.'.
The following U lines each contain two integers r and c, where 1 ≤ r, c ≤ N, representing an update to the cell in the r-th row from the top and the c-th column from the left of the canvas.
Output
Output U+1 lines representing the minimum number of operations before any updates and after each update.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 20 | N ≤ 4 |
| #2 | 30 | U ≤ 10 |
| #3 | 50 | No additional constraints. |
Example
4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4
4
3
2
1
0
1
The following canvas satisfies the reflective condition and differs from the original canvas by 4 operations:
....
####
####
....It is impossible to make the original canvas satisfy the reflective condition using fewer than 4 operations.
After updating (1,3), the canvas looks like this:
....
##.#
####
..##It now takes 3 operations to make the canvas satisfy the reflective condition.
After updating (2,3), the canvas looks like this:
....
####
####
..##It now takes 2 operations to make the canvas satisfy the reflective condition.
You must sign in to write code.