洛谷P1162 填涂颜色——广搜

逃离我推掉我的手 2023-09-26 18:19 37阅读 0赞

> ### 题目描述 ###
> 
> 由数字 0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 构成，围圈时只走上下左右 4 个方向。现要求把闭合圈内的所有空间都填写成 22。例如：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 的完整方阵。
> 
> ### 输入输出样例 ###
> 
> **输入** 
> 
>     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
> 
> ### 说明/提示 ###
> 
> 对于 100% 的数据，1≤n≤30。

#include<iostream>
    #include<queue>
    using namespace std;
    int xx[] = { 0,-1,0,1 };
    int yy[] = { 1,0,-1,0 };
    int mp[40][40];
    bool vis[40][40];
    int n;
    int main()
    {
    	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);
    	y.push(0);
    	vis[0][0] = 1;
    
    	while (!x.empty())
    	{
    		int tx = x.front();
    		int ty = y.front();
    		for (int i = 0; i < 4; i++)
    		{
    			int dx = x.front() + xx[i];
    			int dy = y.front() + yy[i];
    			if (dx >= 0 && dx <= n + 1 && dy >= 0 && dy <= n + 1 && mp[dx][dy] == 0 && !vis[dx][dy])
    			{
    				x.push(dx);
    				y.push(dy);
    				vis[dx][dy] = 1;
    			}
    		}
    		x.pop();
    		y.pop();
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= n; j++)
    		{
    			if (mp[i][j] == 0 && vis[i][j] == 0)
    			{
    				cout << 2 << " ";
    			}
    			else
    			{
    				cout << mp[i][j] << " ";
    			}
    		}
    		cout << endl;
    	}
    
    	return 0;
    }