洛谷P1162 填涂颜色

题目链接：https://www.luogu.org/problemnew/show/P1162

这道题是LITTLESUN写的第一道BFS哦！

对于这道题的的思路是把封闭图形外边的0标记一边，在最后输出的时候把没有标记过的0输出为2，其他按照原图输出。

对于这道题的的边界有两种判断方式。第一种是在原图外面加一圈0

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 2000 
using namespace std;
int G[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct item
{
    int x;
    int y;
};
int n;
item a;
item t2;
void bfs()
{
            queue<item>q;
                a.x=1;
                a.y=1;
                q.push(a);
                while(!q.empty())
                {
                    item t=q.front();
                    q.pop();
                    if(G[t.x+1][t.y]==0&&t.x!=n+2&&!vis[t.x+1][t.y])
                    {
                        vis[t.x+1][t.y]=1;
                        t2.x=t.x+1;
                        t2.y=t.y;
                        q.push(t2);
                    }
                    if(G[t.x-1][t.y]==0&&t.x!=1&&!vis[t.x-1][t.y])
                    {
                        vis[t.x-1][t.y]=1;
                        t2.x=t.x-1;
                        t2.y=t.y;
                        q.push(t2);
                    }
                    if(G[t.x][t.y+1]==0&&t.y!=n+2&&!vis[t.x][t.y+1])
                    {
                        vis[t.x][t.y+1]=1;
                        t2.x=t.x;
                        t2.y=t.y+1;
                        q.push(t2);
                    }    
                    if(G[t.x][t.y-1]==0&&t.y!=1&&!vis[t.x][t.y-1])
                    {
                        vis[t.x][t.y-1]=1;
                        t2.x=t.x;
                        t2.y=t.y-1;
                        q.push(t2);
                    }
                }
            }
    
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n+1;i++)
    {
        for(int j=2;j<=n+1;j++)
        {
            scanf("%d",&G[i][j]);
        }
    }
    bfs();
    for(int i=2;i<=n+1;i++)
    {
        for(int j=2;j<=n+1;j++)
        {
            if(!vis[i][j]&&G[i][j]==0)
            {
                G[i][j]=2;
            }
        }
    }
    for(int i=2;i<=n+1;i++)
    {
        //cout<<endl;
        for(int j=2;j<=n+1;j++)
        {
            printf("%d ",G[i][j]);
        }
        cout<<endl;
    }
    return 0;
}

另一种方法是枚举边界每一个不是一的点作为起点进行BFS

但这个代码不知道哪里锅掉了，只有80分qwq

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 2000 
using namespace std;
int G[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct item
{
    int x;
    int y;
};
int n;
item a;
queue<item> q;
void bfs(item b)
{
    q.push(b);
    while(!q.empty())
    {
        item t=q.front();
        q.pop();
        if(G[t.x+1][t.y]==0&&t.x!=n&&!vis[t.x+1][t.y])
        {
            vis[t.x+1][t.y]=1;
            t.x=t.x+1;
            t.y=t.y;
            q.push(t);
        }
        if(G[t.x-1][t.y]==0&&t.x!=1&&!vis[t.x-1][t.y])
        {
            vis[t.x-1][t.y]=1;
            t.x=t.x-1;
            t.y=t.y;
            q.push(t);
        }
        if(G[t.x][t.y+1]==0&&t.y!=n&&!vis[t.x][t.y+1])
        {
            vis[t.x][t.y+1]=1;
            t.x=t.x;
            t.y=t.y+1;
            q.push(t);
        }    
        if(G[t.x][t.y-1]==0&&t.y!=1&&!vis[t.x][t.y-1])
        {
            vis[t.x][t.y-1]=1;
            t.x=t.x;
            t.y=t.y-1;
            q.push(t);
        }
    }
} 
void work(){
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i==1||i==n||j==1||j==n)&&G[i][j]!=1)
            {
                a.x=i;
                a.y=j;        
                bfs(a);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&G[i][j]);
        }
    }
    work();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!vis[i][j]&&G[i][j]==0)
            {
                G[i][j]=2;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        //cout<<endl;
        for(int j=1;j<=n;j++)
        {
            printf("%d ",G[i][j]);
        }
        cout<<endl;
    }
    return 0;
}