Cloud_LCheny @ 2023-02-13 15:36:54

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dir[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
const int N=10001; 
int a[N][N],b[N][N];

struct node
{
    int x,y;
};
queue<node> q;
void bfs(int x,int y)
{

    int xx,yy;
    node b;
    b.x=x;
    b.y=y;
    q.push(b);
    while(!q.empty())
    {
        node e=q.front();
        q.pop();
        int kx=e.x;
        int ky=e.y;
        for(int i=0;i<4;i++)
        {
            xx=kx+dir[i][0];
            yy=ky+dir[i][1];
            if(xx>0&&xx<=n&&yy>0&&yy<=n&&a[xx][yy]==0)
            {
            a[xx][yy]=2;
            q.push(node{xx,yy});
            }
        }
    }

 } 

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];

        }
    }
    node l;
    bool ll=false;
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
        if(ll)
        break;
        if(a[i][j]==1)
        {
            l.x=i;
            l.y=j;
            ll=true;
            break;
            }   
        }

    }
    bfs(l.x+1,l.y+1);
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }

}

by _JellyFish_ @ 2023-02-13 16:19:47

• 1. 初始点没有涂色，直接涂色到它的相邻点。但是因为 2-5 样例较大，会在涂到旁边点后返回来涂，造成一种没有问题的假象。
• 2. 数据范围 N 只有 30 ，但你开了 1e5 ，甚至将int定义long long，这种做法不是不可以，但在这种题里只会MLE，没有那是运气好，建议尽快修改。
• 3. 此题还需要适当剪枝。

by Loser_Syx @ 2023-02-13 16:24:05

@Cloud_LCheny

1 数据我帮你下载了

3
1 1 1
1 0 1
1 1 1

1 1 1
1 2 1
1 1 1

by Loser_Syx @ 2023-02-13 16:26:53

@Cloud_LCheny 当然，正解代码如下，bfs初始数据错了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dir[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
const int N=10001; 
int a[N][N],b[N][N];

struct node
{
    int x,y;
};
queue<node> q;
void bfs(int x,int y)
{

    int xx,yy;
    node b;
    b.x=x;
    b.y=y;
    q.push(b);
    while(!q.empty())
    {
        node e=q.front();
        q.pop();
        int kx=e.x;
        int ky=e.y;
        for(int i=0;i<4;i++)
        {
            xx=kx+dir[i][0];
            yy=ky+dir[i][1];
            if(xx>0&&xx<=n&&yy>0&&yy<=n&&a[xx][yy]==0)
            {
            a[xx][yy]=2;
            q.push(node{xx,yy});
            }
        }
    }

 } 

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];

        }
    }
    node l;
    bool ll=false;
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
        if(ll)
        break;
        if(a[i][j]==1)
        {
            l.x=i;
            l.y=j;
            ll=true;
            break;
            }   
        }

    }
    bfs(l.x,l.y+1);
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }

}

by Cloud_LCheny @ 2023-02-14 12:21:37

@Saint_ying_xtf 谢谢大佬