Alice and Recoloring 1
Contest: Codeforces Round 746 (Div. 2)
Difficulty rating: 2600
Tags: constructive algorithms, greedy

The difference between the versions is in the costs of operations. Solution for one version won't work for another!

Alice has a grid of size $$$n \times m$$$, initially all its cells are colored white. The cell on the intersection of $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. Alice can do the following operations with this grid:

- Choose any subrectangle containing cell $$$(1, 1)$$$, and flip the colors of all its cells. (Flipping means changing its color from white to black or from black to white). This operation costs $$$1$$$ coin.
- Choose any subrectangle containing cell $$$(n, 1)$$$, and flip the colors of all its cells. This operation costs $$$2$$$ coins.
- Choose any subrectangle containing cell $$$(1, m)$$$, and flip the colors of all its cells. This operation costs $$$4$$$ coins.
- Choose any subrectangle containing cell $$$(n, m)$$$, and flip the colors of all its cells. This operation costs $$$3$$$ coins.

As a reminder, subrectangle is a set of all cells $$$(x, y)$$$ with $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ for some $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$.

Alice wants to obtain her favorite coloring with these operations. What's the smallest number of coins that she would have to spend? It can be shown that it's always possible to transform the initial grid into any other.

Input format:
The first line of the input contains $$$2$$$ integers $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — the dimensions of the grid.

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ of length $$$m$$$, consisting of letters W and B. The $$$j$$$-th character of string $$$s_i$$$ is W if the cell $$$(i, j)$$$ is colored white in the favorite coloring of Alice, and B if it's colored black.

Output format:
Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it's optimal to just apply the fourth operation once to the rectangle containing cells $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$. This would cost $$$3$$$ coins.

Example input:
3 3
WWW
WBB
WBB

Example output:
3

Example input:
10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW

Example output:
74

Editorial:
We will transform favorite coloring to the all-white coloring instead.
Let's denote W by $$$0$$$ and B by $$$1$$$.
First observation is that it doesn't make sense to do operations of type $$$2$$$ and $$$3$$$ at all. Indeed, each of them can be replaced with $$$2$$$ operations of type $$$1$$$:
Instead of flipping subrectangle $$$[x, n]\times[1, y]$$$, we can flip subrectangles $$$[1, n]\times[1, y]$$$ and $$$[1, x-1]\times[1, y]$$$, and similarly for $$$[1, x]\times[y, n]$$$. So, from now on we only consider first and last operations.
Let's create a grid $$$a$$$ of $$$n$$$ rows and $$$m$$$ columns, where $$$a[i][j]$$$ denotes the parity of the sum of numbers in those of cells $$$(i, j), (i+1, j), (i, j+1), (i+1, j+1)$$$ of favorite coloring, which are present on the grid. Clearly, all numbers in $$$a$$$ are $$$0$$$ if and only if current coloring is all $$$0$$$, so we will want to just make the grid $$$a$$$ all $$$0$$$.
Let's look at how first and last operations affect the grid $$$a$$$. If we flip the subrectangle $$$[1, x]\times [1, y]$$$ with the operation of the first type, in grid $$$a$$$ the only value that changes is $$$a[x][y]$$$. If we flip the subrectangle $$$[x, n]\times [y, m]$$$, clearly $$$x, y>1$$$ (otherwise we could have instead used $$$2$$$ operations of the first type). Then, it's easy to see that the only cells that will change are $$$a[x-1][y-1], a[n][y-1], a[x-1][m], a[n][m]$$$.
So, now we have the following problem: we have a binary grid $$$n\times m$$$. In one operation, we can change some $$$1$$$ to $$$0$$$, with cost of $$$1$$$ coin, or to select some $$$1 \le x\le n-1, 1 \le y \le m-1$$$, and flip the numbers in cells $$$a[x][y], a[n][y], a[x][m], a[n][m]$$$ with cost of $$$3$$$ coins. What's the smallest cost to make all numbers $$$0$$$?
Now, it's easy to see that it doesn't make sense to apply second operation more than once, as instead of doing it twice, we can apply the operation of the first type at most $$$6$$$ times (as cell $$$a[n][m]$$$ will be flipped twice). Moreover, it only makes sense to apply the second operation if there exist such $$$1 \le x\le n-1, 1 \le y \le m-1$$$ for which all cells $$$a[x][y], a[n][y], a[x][m], a[n][m]$$$ are $$$1$$$. So, the algorithm would be to calculate the grid $$$a$$$, to calculate the total number of ones in it $$$ans$$$, and substract $$$1$$$ from $$$ans$$$ if there exists such $$$1 \le x\le n-1, 1 \le y \le m-1$$$ for which all cells $$$a[x][y], a[n][y], a[x][m], a[n][m]$$$ are $$$1$$$.
Complexity $$$O(nm)$$$.