AT_abc390_c 题解

· · 题解

题目传送门

题意

找一个长方形，判断其所有格子是否全部为黑色，且没有多余的黑色格子。其中若 (i,j) 点为 ?，可以将其涂为任意黑色或者白色。

思路

由于只有一个长方形，可以求出这个长方形四条边最左侧的黑色格子纵坐标 U，最下侧的黑色格子纵坐标 D，最左侧的黑色格子横坐标 L，最右侧的黑色格子横坐标 R。

这样就得到了一个长方形，其左上角为 (U,L)，右下角为 (D,R)。然后可以遍历这个长方形，由于字符为 ? 的点可以涂成黑色，就将其算作黑色。所以只需判断长方形内有无白色即可，无则输出 Yes，有则输出 No。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10;
char s[N][N];
signed main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    int u=INT_MAX,d=INT_MIN,l=INT_MAX,r=INT_MIN;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i][j]=='#'){
                u=min(u,i),d=max(d,i);
                l=min(l,j),r=max(r,j);
            }
    for(int i=u;i<=d;++i)
        for(int j=l;j<=r;++j)
            if(s[i][j]=='.')
                return printf("No\n"),0;
    printf("Yes\n");
    return 0;
}