有没有大神叫一下蒟蒻这题哪里错了,第三个点没过,其他全过

P1162 填涂颜色

queen_street @ 2021-07-07 11:55:38

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int x,y;
};

queue <node> a;
int s[31][31],b[31][31];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};

int main()
{
    int i,j,n;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>s[i][j];
            if(s[i][j]==1)
            {
                b[i][j]=3;
            }
        }
    }
    node p,p2;
    p.x=1;
    p.y=1;
    p2.x=n;
    p2.y=n;
    a.push(p);
    int newx,newy;
    while(!a.empty())
    {
        node e;
        e=a.front();

        for(i=1;i<=4;i++)
        {
            newx=e.x+dx[i];
            newy=e.y+dy[i];
            if(newx>=1 && newx<=30 && newy>=1 && newy<=30 && b[newx][newy]==0 && s[i][j]==0)
            {
                node k;
                k.x=newx;
                k.y=newy;
                a.push(k);
                b[k.x][k.y]=1;
            }
        }
        a.pop();
    }
    a.push(p2);
    while(!a.empty())
    {
        node e;
        e=a.front();

        for(i=1;i<=4;i++)
        {
            newx=e.x+dx[i];
            newy=e.y+dy[i];
            if(newx>=1 && newx<=30 && newy>=1 && newy<=30 && b[newx][newy]==0 && s[i][j]==0)
            {
                node k;
                k.x=newx;
                k.y=newy;
                a.push(k);
                b[k.x][k.y]=1;
            }
        }
        a.pop();
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(b[i][j]==3)
            {
                cout<<1<<" ";
            }
            else if(b[i][j]==1)
            {
                cout<<0<<" ";
            }
            else if(b[i][j]==0)
            {
                cout<<2<<" "; 
            }

        }
        cout<<endl;
    }
}

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

@queen_street

发点自己的想法:

#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了,别忘了关注哦~


|