提示: 欢迎访问OurACM平台。
Problem 1728 BG Square II

Accept: 36    Submit: 97
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

In the big playground,there are many boys and girls,they just form a N*N square.
A so-called "BG Square" is a square in which all boys are separated by girls and vice versa,ignoring the people outside.
Now wzc wants to find out a M*M "BG Square" in the playground,but there may not exist one.
Fortunately,wzc can change any square into "BG Square" with some cost.
Each time he can replace a boy with a girl at any position and vice versa.
He is wonder what is the minimum changes he has to make in order to get a M*M "BG Square"?

Input

There are multiple test cases.
For each case, the first line is a integers N (1<= N <= 1000),indicating there is a N*N square,
which is made of boys and girls in the playground,M(1<=M<=N),indicating the size of "BG Square" wzc wants.
Followed by N lines,each line contains N char of 'B' or 'G'.
'B' stands for boy,and 'G' for girl.

Output

For each test case, output the least changes that should be made to get a M*M "BG Square".

Sample Input

1 1 B 3 3 BBB BBB BBB 4 3 BGGB GBGB GGBB BGGG

Sample Output

0 4 2

Hint

In the middle sample ,you can make four change to get the target: BGB GBG BGB

Source

FZU 2009 Summer Training Qualification -- Hero Revival 2

Submit  Back  Status  Discuss