【Codeforces Round #423 (Div. 2) B】Black Square

【Link】:http://codeforces.com/contest/828/problem/B

【Description】



给你一个n*m的格子;

里面包含B和W两种颜色的格子;

让你在这个格子中画一个正方形;

(大小,位置自己选 但要求覆盖到所有现有的黑棋子 );

然后,把里面的白棋子,染成黑棋子;

问你最少需要染多少个白棋子;

【Solution】



先得到一个 矩形 (这个矩形 覆盖所有的黑棋子 );

然后枚举所需要的正方形的左上角的位置;

这个正方形必然要覆盖这个 矩形 ;

则这个左上角只能在这个 正方形的左上角 的左上方,或和正方形的左上角重合;

取那个 矩形的右下角 ,只要正方形能够覆盖到右下角,就能覆盖整个矩形;

剩下的就不难写了;

获取正方形 应该有的最小边长 ;

然后统计这个正方形里面W的个数就好;



【NumberOf WA】



0



【Reviw】



做题的时候不用着急:)

慢慢想



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

int n,m,mini = N,maxi = 0,minj = N,maxj = 0;

char s[N][N];

int main(){

    scanf("%d%d",&n,&m);

    rep1(i,1,n) scanf("%s",s[i]+1);

    rep1(i,1,n){

        rep1(j,1,m)

        if (s[i][j]=='B'){

            mini = min(mini,i);

            maxi = max(maxi,i);

            minj = min(minj,j);

            maxj = max(maxj,j);

        }

    }

    if (maxi==0){

        printf("1\n");

        return 0;

    }

    int num = N*N;

    rep1(i,1,n){

        rep1(j,1,m){

            if (i <= mini && j <= minj){

                int lenj = maxj-j+1,leni = maxi-i+1;

                lenj = max(lenj,leni);

                int rj = j + lenj-1,ri = i + lenj -1;

                if (rj > m || ri > n) continue;

                int temp = 0;

                rep1(ii,i,ri)

                    rep1(jj,j,rj)

                        if (s[ii][jj]=='W')

                            temp++;

                num = min(num,temp);

            }

        }

    }

    if (num > n*n)

        printf("-1\n");

    else

        printf("%d\n",num);

    return 0;

}