【Codeforces Round #423 (Div. 2) B】Black Square
Codeforces div round Black Square
2023-09-14 09:03:50 时间
给你一个n*m的格子;
里面包含B和W两种颜色的格子;
让你在这个格子中画一个正方形;
(大小,位置自己选但要求覆盖到所有现有的黑棋子);
然后,把里面的白棋子,染成黑棋子;
问你最少需要染多少个白棋子;
先得到一个矩形(这个矩形覆盖所有的黑棋子);
然后枚举所需要的正方形的左上角的位置;
这个正方形必然要覆盖这个矩形;
则这个左上角只能在这个正方形的左上角的左上方,或和正方形的左上角重合;
取那个矩形的右下角,只要正方形能够覆盖到右下角,就能覆盖整个矩形;
剩下的就不难写了;
获取正方形应该有的最小边长;
然后统计这个正方形里面W的个数就好;
0
做题的时候不用着急:)
慢慢想
#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;
}
相关文章
- 【Codeforces Round #698 (Div. 2) C】Nezzar and Symmetric Array
- 1800*1【Codeforces Round #665 (Div. 2) D】Maximum Distributed Tree
- 【Codeforces Round #639 (Div. 2) C】Hilbert's Hotel
- 【Codeforces Round #667 (Div. 3) F】Subsequences of Length Two
- 【Educational Codeforces Round 88 (Rated for Div. 2) D】Yet Another Yet Another Task
- 【Codeforces Round #645 (Div. 2) F】 Tasty Cookie
- 【Codeforces Round #507 (Div. 2, based on Olympiad of Metropolises) A】Palindrome Dance
- 【Codeforces Round #459 (Div. 2) B】 Radio Station
- 【Codeforces Round #459 (Div. 2) D】MADMAX
- 【Codeforces Round #301 (Div. 2) A】 Combination Lock
- 【74.89%】【codeforces 551A】GukiZ and Contest
- 【Codeforces Round #437 (Div. 2) B】Save the problem!
- 【Codeforces Round #427 (Div. 2) A】Key races
- 【Codeforces Round #421 (Div. 2) B】Mister B and Angle in Polygon
- Codeforces Round #274 (Div. 2)
- Codeforces Round #256 (Div. 2) D. Multiplication Table 二分法
- Codeforces Round #258 (Div. 2/B)/Codeforces451B_Sort the Array
- Codeforces Beta Round #25 (Div. 2)--A. IQ test
- Codeforces Round #418 (Div. 2)
- 补题:Codeforces Round 858 (Div. 2) C. Sequence Master