求助大佬

P1162 填涂颜色

江户川コナン @ 2021-07-26 18:03:59

求助!只有64pts,第4个和第6个点WA

代码:

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    node(int xx,int yy){
        x=xx;
        y=yy;
    }
};
const int maxn=35;
int d[5][2]={{-1,0},{1,0},{0,-1},{0,1}};
int a[maxn][maxn];
bool b[maxn][maxn];
int n;
bool in(int dx,int dy){
    return (dx>=1)&&(dx<=n)&&(dy>=1)&&(dy<=n);
}
void bfs(int x,int y){
    queue<node> q;
    q.push(node(x,y));
    //cout<<x<<" "<<y<<endl;
    b[x][y]=true;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=1;i<=4;i++){
            int dx=now.x+d[i][0];
            int dy=now.y+d[i][1];
            if(in(dx,dy)&&!b[dx][dy]&&a[dx][dy]!=1){
                q.push(node(dx,dy));
                //cout<<dx<<" "<<dy<<endl;
                b[dx][dy]=true;
            }
        }
    }
}
int main(){
    cin>>n;
    //memset(a,1,sizeof a);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    //cout<<1<<endl;
    for(int i=1;i<=n;i++){
        if(a[1][i]==0 &&!b[1][i]){
            bfs(1,i);
        }
        //cout<<1<<endl;
        if(a[n][i]==0&&!b[n][i]){
            bfs(n,i);
        }
        //cout<<2<<endl;
        if(a[i][1]==0&&!b[i][1]){
            bfs(i,1);
        }
        //cout<<3<<endl;
        if(a[i][n]==0&&!b[i][n]){
            bfs(i,n);
        }
        //cout<<4<<endl;
    }
    //bfs();
    //cout<<1<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]!=1&&!b[i][j]){
                cout<<2<<" ";
            }else{
                cout<<a[i][j]<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

大致思路是说用BFS将不被包围的0全部标记起来,然后没被标记的0输出2,其他照旧

恳请各位大佬指点迷津


by WangYinxiAlex @ 2023-07-31 14:51:22

@江户川コナン

发点自己的想法:

#include<iostream>
using namespace std;
int a[31][31];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1)a[i][j]=2;
        }
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=n-1;i>1;i--){
        for(int j=n-1;j>1;j--){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

注释:

10-14行:由于最多矩形的边缘也是在最外面一周,所以最外面的0肯定都不是矩阵内的。
15-23行:从左、上方向判断这个点四周是不是有矩形外的点(0),如果有,说明这个点也不是矩形内的。
24-32行:但只从左、上方向看是不够的(如图1,这个是左、上方向的漏洞),还得从右、下方向判断。
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
图1
(第3行第2列、第3行第3列、第4行第2列、第4行第3列、第4行第4列均无法被赋值)

按照这个办法,可以AC

如果AC了,别忘了关注哦~


|