题意:

给一张表,将被1圈起来的0填为2

模拟:

原图:
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
给边界DFS后的图:
1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
改为2的图:
1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 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,将边界的0消掉(换成1)

原图所有0改为2

原图为2的地方备份图也改为2

输出备份图

歹马:

#include<iostream>
using namespace std;
//相对方位
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
int n;
int g[40][40],t[40][40];//图和备份图
bool f[40][40];//标记图
void dfs(int a,int b)//深度优先标记
{
	f[a][b]=true;//标记
	g[a][b]=1;//改为1
	for(int i=0;i<4;i++)//4个方位
	{
        //是否越界与是否是0
		if(a+x[i]>=0 && a+x[i]<n && b+y[i]>=0 && b+y[i]<n && f[a+x[i]][b+y[i]]==false && g[a+x[i]][b+y[i]]==0)
		{
			dfs(a+x[i],b+y[i]);//递归
		}
	}
}
int main()
{
	cin>>n;//输入
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int x;
			cin>>x;//输入
			g[i][j]=x;//设置
			t[i][j]=x;//备份设置
		}
	}
	for(int i=0;i<n;i++)//最上的
	{
		if(f[0][i]==false && g[0][i]==0)
		{
			dfs(0,i);
		}
	}
	for(int i=0;i<n;i++)//最下的
	{
		if(f[n-1][i]==false && g[n-1][i]==0)
		{
			dfs(n-1,i);
		}
	}
	for(int i=0;i<n;i++)//最左的
	{
		if(f[i][0]==false && g[i][0]==0)
		{
			dfs(i,0);
		}
	}
	for(int i=0;i<n;i++)//最右的
	{
		if(f[i][n-1]==false && g[i][n-1]==0)
		{
			dfs(i,n-1);
		}
	}
	for(int i=0;i<n;i++)//把剩下的0填成2
	{
		for(int j=0;j<n;j++)
		{
			if(g[i][j]==0)
			{
				t[i][j]=2;
			}
		}
	}
	for(int i=0;i<n;i++)//输出填过的
	{
		for(int j=0;j<n;j++)
		{
			cout<<t[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;//完结散花
}

#include<iostream>
using namespace std;
int a[100][100],b[100][100];
int n,x,y;
void dfs(int x,int y){
    if(x>n||x<1||y>n||y<1||a[x][y]!=0)return ;
    a[x][y]=1;
    dfs(x+1,y),dfs(x-1,y),dfs(x,y+1),dfs(x,y-1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]==1) b[i][j]=-1;
        }
	}
    int flag=0;
    for(int i=1;i<=n;i++){
	    if(a[i][1]!=1) dfs(i,1);
	    if(a[i][n]!=1) dfs(i,n);
    }
    for(int i=1;i<=n;i++){
    	if(a[1][i]!=1) dfs(1,i);
    	if(a[n][i]!=1) dfs(n,i);
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(b[i][j]==-1) cout<<"1 ";
            else if(a[i][j]==0) cout<<"2 ";
            else cout<<"0 ";
        }
        cout<<endl;
    }
    return 0;
}

题意

输入一个 $n \times n$ 方阵，把方阵里被 1 围起来的区域变成 2，然后输出填完 2 的方阵

思路

把被围起来以外的区域填成墙壁，剩下的区域就是 2 的地方

代码

#include <bits/stdc++.h>
using namespace std;
int a[35][35],b[35][35];	// a 为原图，b 为备份 
bool f[35][35];
void init(){
	for (int i = 0;i < 35;i++){
		fill(a[i],a[i] + 35,1);
	}
}
void dfs(int i,int j){
	f[i][j] = 1;	// 标记 
	a[i][j] = 1;	// 填充成墙壁 
	if (!a[i - 1][j] && !f[i - 1][j])	dfs(i - 1,j);	// 如果上面不是墙壁，就填充它 
	if (!a[i][j - 1] && !f[i][j - 1])	dfs(i,j - 1);	// 左边同理 
	if (!a[i + 1][j] && !f[i + 1][j])	dfs(i + 1,j);	// 下面同理 
	if (!a[i][j + 1] && !f[i][j + 1])	dfs(i,j + 1);	// 右边同理 
}
int main(int argc, char **argv){
	init();	// 将区域范围外填成墙壁 
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){	// 输入原图和备份图 
		for (int j = 1;j <= n;j++){
			cin >> a[i][j];
			b[i][j] = a[i][j];
		}
	}

	for (int i = 1;i <= n;i++){	// 最上一行遍历 
		if (!a[1][i] && !f[1][i])	dfs(1,i);
	} 
	for (int i = 1;i <= n;i++){	// 最左一列遍历
		if (!a[i][1] && !f[i][1])	dfs(i,1);
	} 
	for (int i = 1;i <= n;i++){	// 最下一行遍历
		if (!a[n][i] && !f[n][i])	dfs(n,i);
	} 
	for (int i = 1;i <= n;i++){	// 最右一列遍历
		if (!a[i][n] && !f[i][n])	dfs(i,n);
	} 

	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= n;j++){
			printf("%d ",a[i][j]?b[i][j]:2);	// 如果原图为 0，就输出 2（被围起来之外的） 
		}
		cout << "\n";
	}
	return 0;
}

样例

样例 1：

输入：

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

过程：

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

输出：

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

样例2

输入：

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

过程：

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

输出：

1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 2 2 2 2 1
1 2 2 2 2 2 1
1 2 2 2 2 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1

#include<bits/stdc++.h>
#define long long long
using namespace std;
const int N=2e2;//可更改。 
template<typename any>
struct Queue{
	any a[N];
	int head=0;
	int tail=0;
	void push(any x){
		a[tail++]=x;
	}
	void pop(){
		head++;
	}
	any vpop(){
		head++;
		return a[head-1];
	}
	bool nothing(){
		if(head-tail);
		else{
			head=0;
			tail=0;
		}
		return head==tail;
	}
};
template<typename any>
struct Stack{
	any a[N];
	int top=0;
	void push(any x){
		a[top++]=x;
	}
	void pop(){
		top--;
	}
	any vpop(){
		top--;
		return a[top+1];
	}
};
int a[N][N];
int b[N][N];
void DFS(int i,int j,int n){
	a[i][j]=1;
	if(!a[i+1][j]&&i+1<=n)
	DFS(i+1,j,n);
	if(!a[i-1][j]&&i-1>0)
	DFS(i-1,j,n);
	if(!a[i][j+1]&&j+1<=n)
	DFS(i,j+1,n);
	if(!a[i][j-1]&&j-1>0)
	DFS(i,j-1,n);
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		cin>>a[i][j];
		b[i][j]=a[i][j];
	}
	for(int i=1;i<=n;i++){
		if(!a[i][1])
		DFS(i,1,n);
		if(!a[i][n])
		DFS(i,n,n);
		if(!a[1][i])
		DFS(1,i,n);
		if(!a[n][i])
		DFS(n,i,n);
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(!a[i][j])
	b[i][j]=2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		cout<<b[i][j]<<" ";
		cout<<"\n";
	}
}