首页 > 代码库 > Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) B. Black Square

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) B. Black Square

2024-10-24 07:47:01   209人阅读

题意：问是否可以形成一个全黑正方形

思路：可以找出正方形的边，然后判断下这个矩阵是否容得下，n，m都比边短，比赛的时候写麻烦了，还去找了这个正方形究竟在哪个位置，这样的话得考虑很多情况，不如就边*边-黑子的总数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=2e5+10;
 5 char a[102][102];
 6 int main(){
 7     int n,m;
 8     scanf("%d%d",&n,&m);
 9     for(int i=1;i<=n;i++){
10         scanf("%s",a[i]+1);
11     }
12     int hl=100000,hr=0,ll=100000,lr=0;
13     int xx=0;
14     for(int i=1;i<=n;i++){
15         for(int j=1;j<=m;j++){
16             if(a[i][j]==‘B‘){
17                 hr=max(hr,j);
18                 hl=min(hl,j);xx++;
19             }
20         }
21     }
22     for(int j=1;j<=m;j++){
23         for(int i=1;i<=n;i++){
24             if(a[i][j]==‘B‘){
25                 lr=max(lr,i);
26                 ll=min(ll,i);
27             }
28         }
29     }
30     int len=max(hr-hl+1,lr-ll+1);
31     if(xx==0){
32         cout<<1<<endl;return 0;
33     }
34     if(len*len>n*m||len>n||len>m){
35         cout<<-1<<endl;
36     }
37     else cout<<len*len-xx<<endl;
38 
39 }

 

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) B. Black Square


联系
我们