P1162 填涂颜色

我的思路（还是想了些许时间的）：
按照题目的闭合圈的规定：

• 闭合圈由数字1构成
• 围圈时只走上下左右4个方向
• 方阵内只有一个闭合圈，圈内至少有一个0

可知从上到下， 从左到右遍历到第一个为1的格子的右下角必定为圈内的0，然后就是bfs填充连通块了

const int N=35;
int g[N][N];
PII st;
int n;

inline bool check(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<n;
}

void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    g[x][y]=2;

    while(q.size())
    {
        PII t=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            int a=t.fi+dx[i],b=t.se+dy[i];
            if(check(a,b) && !g[a][b])
            {
                g[a][b]=2;
                q.push({a,b});
            }
        }
    }
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(g[i][j] == 1)
            {
                st.fi=i,st.se=j;
                goto bfs;
            }

bfs:
    bfs(st.fi+1,st.se+1);

    for(int i=0;i<n;i++,cout<<endl)
        for(int j=0;j<n;j++)
            cout<<g[i][j]<<‘ ‘;
    //system("pause");
}

大部分题解做法：
在外面围一圈0

const int N=35;
int g[N][N];
bool vis[N][N];
PII st;
int n;

inline bool check(int x,int y)
{
    return x>=0 && x<=n+1 && y>=0 && y<=n+1;
}

void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    vis[x][y]=true;

    while(q.size())
    {
        PII t=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            int a=t.fi+dx[i],b=t.se+dy[i];
            if(check(a,b) && !g[a][b] && !vis[a][b])
            {
                vis[a][b]=true;
                q.push({a,b});
            }
        }
    }
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];

    bfs(0,0);

    for(int i=1;i<=n;i++,cout<<endl)
        for(int j=1;j<=n;j++)
            if(!g[i][j] && !vis[i][j])
                cout<<2<<‘ ‘;
            else
                cout<<g[i][j]<<‘ ‘;
    //system("pause");
}

P1162 填涂颜色

原文：https://www.cnblogs.com/fxh0707/p/13696234.html