CF1722F L-shapes题解

lihanwen12 · 2022-09-01 08:40:10 · 题解

题目大意：
定义 L 型为 2\times 2 的格子缺了任意一个角。现在给定一个 n 行 m 列的由 . 或者 * 构成的矩形，询问这个矩形是否由若干个 L 型构成且这些 L 型之间没有点或者边相接触。

解题思路：
扫描每一个格子，看它是否能作为 L 型的一角。如果可以，检查这个 L 型四周与其点或者边相接触的格子有没有字符 *，然后将构成这个 L 型的三个格子标记为使用过。最终如果每一个字符 * 所在的格子都被标记为使用过并且没有发生 L 型与其他格子点或者边相接触则按照题目要求输出 YES 否则输出 NO。

代码：

#include<bits/stdc++.h>
using namespace std;
long long read(){
    long long x=0,sgn=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*sgn;
}
void write(long long n,bool p){
    if(n<0){putchar('-');n=-n;}
    if(n==0){if(p)putchar('0');return;}
    write(n/10,0);putchar(n%10+'0');
}
long long t,n,m,leixing;
char ch[60][60];
bool f[60][60];
bool ans;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=50;i++)
            for(int j=1;j<=50;j++)
                ch[i][j]='.';
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>ch[i][j];
        memset(f,0,sizeof(f));
        ans=true;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                leixing=0;
                if(ch[i][j]=='*'){
                    if(ch[i-1][j]==ch[i][j] && ch[i][j+1]==ch[i][j])leixing=1;
                    if(ch[i-1][j]==ch[i][j] && ch[i][j-1]==ch[i][j])leixing=2;
                    if(ch[i][j-1]==ch[i][j] && ch[i+1][j]==ch[i][j])leixing=3;
                    if(ch[i][j+1]==ch[i][j] && ch[i+1][j]==ch[i][j])leixing=4;
                    if(leixing==1){
                        f[i][j]=1;
                        f[i-1][j]=1;
                        f[i][j+1]=1;
                    }
                    if(leixing==2){
                        f[i][j]=1;
                        f[i-1][j]=1;
                        f[i][j-1]=1;
                    }
                    if(leixing==3){
                        f[i][j]=1;
                        f[i][j-1]=1;
                        f[i+1][j]=1;
                    }
                    if(leixing==4){
                        f[i][j]=1;
                        f[i][j+1]=1;
                        f[i+1][j]=1;
                    }
                }
                if(leixing==1){
                    for(int x=i-2;x<=i+1;x++)
                        for(int y=j-1;y<=j+2;y++){
                            if(x==i-2 && y==j+2)continue;
                            if(x==i && y==j)continue;
                            if(x==i-1 && y==j)continue;
                            if(x==i && y==j+1)continue;
                            if(x>=1 && x<=n && y>=1 && y<=m)
                                if(ch[x][y]=='*')ans=false;
                        }
                }
                if(leixing==2){
                    for(int x=i-2;x<=i+1;x++)
                        for(int y=j-2;y<=j+1;y++){
                            if(x==i-2 && y==j-2)continue;
                            if(x==i && y==j)continue;
                            if(x==i-1 && y==j)continue;
                            if(x==i && y==j-1)continue;
                            if(x>=1 && x<=n && y>=1 && y<=m)
                                if(ch[x][y]=='*')ans=false;
                        }
                }
                if(leixing==3){
                    for(int x=i-1;x<=i+2;x++)
                        for(int y=j-2;y<=j+1;y++){
                            if(x==i+2 && y==j-2)continue;
                            if(x==i && y==j)continue;
                            if(x==i && y==j-1)continue;
                            if(x==i+1 && y==j)continue;
                            if(x>=1 && x<=n && y>=1 && y<=m)
                                if(ch[x][y]=='*')ans=false;
                        }
                }
                if(leixing==4){
                    for(int x=i-1;x<=i+2;x++)
                        for(int y=j-1;y<=j+2;y++){
                            if(x==i+2 && y==j+2)continue;
                            if(x==i && y==j)continue;
                            if(x==i && y==j+1)continue;
                            if(x==i+1 && y==j)continue;
                            if(x>=1 && x<=n && y>=1 && y<=m)
                                if(ch[x][y]=='*')ans=false;
                        }
                }
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(ch[i][j]=='*' && f[i][j]==0)ans=false;
        if(ans)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}