Contents
Alice and Recoloring 2 solution codeforces

For Solution
Click Here!
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×mn×m, initially all its cells are colored white. The cell on the intersection of iith row and jjth column is denoted as (i,j)(i,j). Alice can do the following operations with this grid:
 Choose any subrectangle containing cell (1,1)(1,1), and flip the colors of all its cells. (Flipping means changing its color from white to black or from black to white). Alice and Recoloring 2 solution codeforces
This operation costs 11 coin.
 Choose any subrectangle containing cell (n,1)(n,1), and flip the colors of all its cells.
This operation costs 33 coins.
 Choose any subrectangle containing cell (1,m)(1,m), and flip the colors of all its cells.
This operation costs 44 coins.
 Choose any subrectangle containing cell (n,m)(n,m), and flip the colors of all its cells.
This operation costs 22 coins.
As a reminder, subrectangle is a set of all cells (x,y)(x,y) with x1≤x≤x2x1≤x≤x2, y1≤y≤y2y1≤y≤y2 for some 1≤x1≤x2≤n1≤x1≤x2≤n, 1≤y1≤y2≤m1≤y1≤y2≤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.
Alice and Recoloring 2 solution codeforces
The first line of the input contains 22 integers n,mn,m (1≤n,m≤5001≤n,m≤500) — the dimensions of the grid.
The iith of the next nn lines contains a string sisi of length mm, consisting of letters W and B. The jjth character of string sisi is W if the cell (i,j)(i,j) is colored white in the favorite coloring of Alice, and B if it’s colored black.
Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.
Alice and Recoloring 2 solution codeforces
3 3 WWW WBB WBB
2
Alice and Recoloring 2 solution codeforces
10 15 WWWBBBWBBBBBWWW BBBBWWWBBWWWBBB BBBWWBWBBBWWWBB BBWBWBBWWWBBWBW BBBBWWWBBBWWWBB BWBBWWBBBBBBWWW WBWWBBBBWWBBBWW WWBWWWWBBWWBWWW BWBWWBWWWWWWBWB BBBWBWBWBBBWWBW
68
Alice and Recoloring 2 solution codeforces
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)(2,2),(2,3),(3,2),(3,3). This would cost 22 coins.

For Solution
Click Here!