P1162 填涂颜色

时间：2020-02-10 17:16:55 收藏：0 阅读：64

题目描述

由数字 $\times 66×6的方阵（n=6n=6n=6），涂色前和涂色后的方阵如下：$

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

前几天都在做dfs（然并卵）
今天换换口味，做bfs（然而你做不起）
咳咳，好了言归正传
如果说dfs是不撞南墙不回头，那bfs就是地毯式搜索
这道题我的思路是搜索不再圈内的0，记录下来，输出时再来一个判断
因为搜索面比较广，所以明显bfs更加合适
确定好了基本思路，要先把几个细节想清楚：
题目指出：有一任意形状闭合圈
所以，所有的1形成了一个环
因此，我们可以发现：最外围的一圈0，无论在什么位置，都在环外
所以我们就把最外层的0全部当作bfs的起点，如下：

for(int i=1;i<=n;i++)//把边上的所有点都进行搜索 
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1||j==1||i==n||j==n)//不能在1之间 
            {
                if(a[i][j]==0)
                {
                    q.push(i);
                    q.push(j);
                    s[i][j]=1;//细节见匠心 
                }    
            }    
        }
    }

有了bfs的起点，接下来就只用向上下左右搜索就好了

（不能越界哦~）

代码实现：

while(!q.empty())//如果队列为空，则结束bfs
    {
    int x=q.front();//把没有围起来的点记录下来 
    q.pop();
    int y=q.front();
    q.pop();
    s[x][y]=1;
    //cout<<x<<" "<<y<<endl; 
    if(x>=1&&y-1>=1)//向上走，并且不能越界,也不能走过 
    {
    if(a[x][y-1]==0&&s[x][y-1]==0)
    {
        q.push(x);
        q.push(y-1);
        s[x][y-1]=1;    
    } 
    } 
    if(x>=1&&y+1>=1)//向下走，并且不能越界,也不能走过
    {
    if(a[x][y+1]==0&&s[x][y+1]==0)
    {
        q.push(x);
        q.push(y+1);
        s[x][y+1]=1;    
    } 
    } 
    if(x-1>=1&&y>=1)//向左走，并且不能越界,也不能走过
    {
    if(a[x-1][y]==0&&s[x-1][y]==0)
    {
        q.push(x-1);
        q.push(y);
        s[x-1][y]=1;    
    } 
    } 
    if(x+1>=1&&y>=1)//向右走，并且不能越界,也不能走过
    {
    if(a[x+1][y]==0&&s[x+1][y]==0)
    {
        q.push(x+1);
        q.push(y);
        s[x+1][y]=1;    
    } 
    }      
    }

这里要用到队列，bfs结束的标志就是队列空掉，也意味着所有环外的零都被找完了

记得弹出~

上下左右的过程也可以用一个数组来实现，比较方便，但会被警告

奉上完整代码：

#include<bits/stdc++.h>
#include<queue>//bfs用栈实现 
using namespace std;
int n;//地图的大小 
queue<int>q;
int a[45][45];//涂色的地图
int s[45][45];//用于标记点  
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)//小心打错 
        {
            cin>>a[i][j];//输入地图
        }
    } 
    for(int i=1;i<=n;i++)//把边上的所有点都进行搜索 
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1||j==1||i==n||j==n)//不能在1之间 
            {
                if(a[i][j]==0)
                {
                    q.push(i);
                    q.push(j);
                    s[i][j]=1;//细节见匠心 
                }    
            }    
        }
    }
    while(!q.empty())//如果队列为空，则结束bfs
    {
    int x=q.front();//把没有围起来的点记录下来 
    q.pop();
    int y=q.front();
    q.pop();
    s[x][y]=1;
    //cout<<x<<" "<<y<<endl; 
    if(x>=1&&y-1>=1)//向上走，并且不能越界,也不能走过 
    {
    if(a[x][y-1]==0&&s[x][y-1]==0)
    {
        q.push(x);
        q.push(y-1);
        s[x][y-1]=1;    
    } 
    } 
    if(x>=1&&y+1>=1)//向下走，并且不能越界,也不能走过
    {
    if(a[x][y+1]==0&&s[x][y+1]==0)
    {
        q.push(x);
        q.push(y+1);
        s[x][y+1]=1;    
    } 
    } 
    if(x-1>=1&&y>=1)//向左走，并且不能越界,也不能走过
    {
    if(a[x-1][y]==0&&s[x-1][y]==0)
    {
        q.push(x-1);
        q.push(y);
        s[x-1][y]=1;    
    } 
    } 
    if(x+1>=1&&y>=1)//向右走，并且不能越界,也不能走过
    {
    if(a[x+1][y]==0&&s[x+1][y]==0)
    {
        q.push(x+1);
        q.push(y);
        s[x+1][y]=1;    
    } 
    }      
    } 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i][j]==0&&a[i][j]==0)//如果它是0，还被围起来了，输出2 
            {
                cout<<2<<" ";
            }
            else{
                cout<<a[i][j]<<" ";//正常输出 
            }
            //cout<<s[i][j]<<" ";
        }
        cout<<endl; 
    } 
    return 0;//差点忘打 
}

（弱弱的说一句，这个程序只有84分，有一个点下载样例是对的，但交上去就RE了，仅供娱乐）

（最后我其实打了个表）

完结撒花~

求赞求关注，好人一生平安！

原文：https://www.cnblogs.com/zhangzhiyuan123/p/12291173.html