BFS（广度优先搜索）----洛谷--填涂颜色

分手后的思念是犯贱 2023-06-29 05:55 12阅读 0赞

## 题目 ##

[题目链接][Link 1]  
题目描述  
由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=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  
输入格式  
每组测试数据第一行一个整数n(1≤n≤30)

接下来n行，由0和1组成的n×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

输出格式  
已经填好数字2的完整方阵。

输入输出样例  
输入 \#1 复制  
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  
输出 \#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  
说明/提示  
1≤n≤30

本题的解题思路如下：  
1.首先要先创建一个地图。  
2.这个地图的外围必须是由0包围，比如说创建一个二维数组，要求的大小是n行n列，那么，0行和0列还有n+1行和n+1列对应的数组元素都应该为0，否则会出现  
0 0 0 0 0  
0 0 1 1 1  
1 1 1 1 1  
1 0 0 0 0

0 0 0 0 0  
0 0 1 1 1  
1 1 1 1 1  
1 2 2 2 2  
的错误结果  
3.下面就是广度优先搜索了，建立一个vis的二维数组（与地图等大），用于判断该点是否访问过。  
4.将（0，0）输入到队列坐标中，作为起始位置。这样可以避免（1，1）坐标对应的元素为1，一开始就停止，导致错误结果。  
5.将符合以下条件的压入队列（dx,dy是对应的横纵坐标）  
dx>=0&&dy>=0&&dx<=n+1&&dy<=n+1&&!vis\[dx\]\[dy\]&&!mp\[dx\]\[dy\]  
大致意思是，横纵坐标不能在n+1大小地图的外面，还有就是该点的值不可以为1且未被访问过。  
6.将队首元素出队。  
7.将值为0且未被访问过的元素置为2；  
8输出图。

代码如下

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    using namespace std;
    #define ll long long
    int xx[4]={
        0,1,-1,0};
    int yy[4]={
        1,0,0,-1};
    int mp[33][33];
    bool vis[33][33];
    int main()
    {
        
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        //创建地图
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    }
    queue<int>x;
    queue<int>y;
    x.push(0);//初始化队列坐标为0，0
    y.push(0);
    while(!x.empty()&&!y.empty()){
        //还有结点
    for(int i=0;i<4;i++)
    {
        
        int dx,dy;
        dx=x.front()+xx[i];
        dy=y.front()+yy[i];
        if(dx>=0&&dy>=0&&dx<=n+1&&dy<=n+1&&!vis[dx][dy]&&!mp[dx][dy])//找到符合的坐标
        {
        
            vis[dx][dy]=true;
            x.push(dx);
            y.push(dy);
        }
    }
    x.pop();//将队列头处的元素移出
    y.pop();
    }
    for(int i=1;i<=n;i++)//将1包围圈中的0转换为1
    {
        
        for(int j=1;j<=n;j++)
        {
        
            if(!vis[i][j]&&!mp[i][j])
            {
        
                mp[i][j]=2;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        
        for(int j=1;j<=n;j++){
        
                if(j!=n)
            cout<<mp[i][j]<<" ";
        else cout<<mp[i][j];
        }
            if(i!=n)
        cout<<'\n';
    }
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1162