Codah ClubTrain. Submit. Improve.
Sign in
English
#0004B9

O-Chequered Flag

On their favorite subject: painting, Miloš, Filip i Milan just get a extra task to pass exam. For the incoming race over Sombor town, big chequered flag is about to be made. Flag will be R by C dimensioned, as on all car racing flag is made of square black and white units. No budget for this job, only old parts of wrong painted flags by previous generation.


After they finished flag, big surprise come. Flag is not colored as needed. Goal is to paint flag in such way that no neighbors units of same color (neighbors are next four fields: left, right, up or down, border units has three neighbors and corner units just two).


Remaining job is only painting this flag in proper color. Condition that make this exam passed are to use as minimum color as possible.


Image: confused

InputFirst row: two integers separated with blank space R i [], number of rows and columns on flag (1 <= R,C <= 3000).
Next R rows contain C characters ’C’ or ’B’ (no space between).

OutputFirst and only row: one integer represent minimal square units of flag to be repainted in in such way to make flag chequered.

Input:
[c]3 3
CCC
CCC
CCC
Output:
4


Input:
3 4
CBCB
BCBC
CBCB
Output:
0

Input:
4 2
BC
BC
CB
BC
Output:
2

NOTICE: no meter whether left up square unit of flag is white or black.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.