P1162 填涂颜色

迷南。 2022-05-19 05:57 125阅读 0赞

## 题目描述 ##

由数字 00 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 11 构成，围圈时只走上下左右 44 个方向。现要求把闭合圈内的所有空间都填写成 22 .例如： 6 \\times 66×6 的方阵（ n=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

## 输入输出格式 ##

**输入格式：**

每组测试数据第一行一个整数 n(1 \\le n \\le 30)n(1≤n≤30)

接下来 nn 行，由 00 和 11 组成的 n \\times nn×n 的方阵。

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

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

**输出格式：**

已经填好数字 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

本题诗广度搜索的典型例子

掳代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstdlib>
    #include<queue>
    using namespace std;
    struct site{
    	int x;
    	int y; 
    } exmp,temp;
    int n; 
    const int MAXN=31;
    int A[MAXN][MAXN],B[MAXN][MAXN];
    bool vis[MAXN][MAXN];
    queue<struct site> p;
    
    void dfs(int a,int b)//广度搜索 
    {
    	int i,j,k; 
    	exmp.x=a;
    	exmp.y=b;
    	p.push(exmp);
    	while(!p.empty()){
    		 
    		temp=p.front();
    		p.pop() ; 
    		int x1=temp.x,y1=temp.y; 
    		if(A[x1+1][y1]==0&&x1!=n&&!vis[x1+1][y1]) {
    			vis[x1+1][y1]=1; 
    			temp.x=x1+1;temp.y=y1;p.push(temp); 
    		} 
    		if(A[x1-1][y1]==0&&x1!=1&&!vis[x1-1][y1]) {
    			vis[x1-1][y1]=1; 
    			temp.x=x1-1;temp.y=y1;p.push(temp); 
    		} 
    		if(A[x1][y1+1]==0&&y1!=n&&!vis[x1][y1+1]) {
    			vis[x1][y1+1]=1; 
    			temp.x=x1;temp.y=y1+1;p.push(temp); 
    		} 
    		if(A[x1][y1-1]==0&&y1!=1&&!vis[x1][y1-1]) {
    			vis[x1][y1-1]=1; 
    			temp.x=x1;temp.y=y1-1;p.push(temp); 
    		} 
    	}	
    }
    
    
     int main()
     {
     	int i,j; 
     	scanf("%d",&n);
     	for(int i=1;i<=n;i++)
     		for(int j=1;j<=n;j++){
     			scanf("%d",&A[i][j]);
     			B[i][j]=A[i][j]; 
     			if(A[i][j]==1) vis[i][j]=1;
    		 }
     	for(i=1;i<=n;i=i+n-1)
    	 for(j=1;j<=n;j++)
    	 	if(!vis[i][j]) 
    	 		dfs(i,j); 
     	 
     	 for(i=1;i<=n;i=i+n-1)
    	 for(j=1;j<=n;j++)
    	 	if(!vis[j][i]) 
    	 		dfs(j,i);
    	 		
    	for(i=1;i<=n;i++){ 
    		for(j=1;j<=n;j++)
    			if(!vis[i][j]) cout<<"2"<<" " ;
    			else cout <<B[i][j]<<" ";  		
    		cout<<endl; 
    		} 
    		system("pause");
    	return 0; 
     }