2.14寒假

这几天复习的搜索把之前做过的题目看了一下。

解析：int dx[5]={0,0,1,0,-1}; 和 int dy[5]={0,1,0,-1,0};：这两个数组用于表示上下左右四个方向的偏移量，方便在 DFS 中访问相邻的元素。o 和 p 分别表示当前搜索位置的行和列。边界条件判断：如果当前位置超出矩阵范围（o<0||o>n+1||p<0||p>n+1）或者当前位置的值不为 0，则直接返回。标记当前位置：将当前位置的值标记为 1，表示该位置已经被访问过。递归搜索相邻位置：通过 dx 和 dy 数组遍历当前位置的上下左右四个相邻位置，并递归调用 dfs 函数进行搜索。首先读取矩阵的大小 n，然后使用双重循环读取 n x n 的矩阵元素，并将其存储在数组 a 中，同时将 a 中的元素复制到数组 b 中。从边界开始进行深度优先搜索：分别从矩阵的上下左右边界开始调用 dfs 函数进行搜索，将与边界相连的所有 0 标记为 1。替换未标记的 0：遍历数组 a，如果某个位置的值仍然为 0，说明该位置被 1 完全包围，将数组 b 中对应位置的值替换为 2。
输出结果：使用双重循环遍历数组 b，并输出处理后的矩阵。

#include<stdio.h>
int a[30][30],b[30][30];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int n;
void dfs(int o,int p)
{
	int i;
	if(o<0||o>n+1||p<0||p>n+1||a[o][p]!=0){
		return;
	}
	a[o][p]=1;
	for(i=1;i<=4;i++){
		dfs(o+dx[i],p+dy[i]);
	}
}

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%d",&a[i][j]);
			b[i][j]=a[i][j];
		}
	}
	for(i=0;i<n;i++)
	dfs(0,i);
	for(i=0;i<n;i++)
	dfs(n-1,i);
	for(i=0;i<n;i++)
	dfs(i,0);
	for(i=0;i<n;i++)
	dfs(i,n-1);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(a[i][j]==0)
			b[i][j]=2;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++)
		printf("%d ",b[i][j]);
		printf("\n");
	}
	return 0;
}

解析：使用双重循环遍历整个二维网格。当遇到字符不为 '0' 的位置时，调用 dfs 函数进行深度优先搜索，将该连通区域的所有 '1' 标记为 '0'。每完成一次 dfs 搜索，就意味着找到了一个新的连通区域，count 加 1。

#include<stdio.h>
int n,m,count=0;
char a[101][101];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};

void dfs(int x,int y)
{
	int i;
	if(x<1||x>n||y<1||y>m||a[x][y]=='0')
	return;
	a[x][y]='0';
	for(i=1;i<=4;i++){
		dfs(x+dx[i],y+dy[i]);
	}
}

int main() 
{
	int i,j;
	scanf("%d %d",&n,&m);
	for(i=1; i<=n; i++) {
		for(j=1; j<=m; j++) {
			scanf(" %c",&a[i][j]);
		}
	}
	for(i=1; i<=n; i++) {
		for(j=1; j<=m; j++) {
			if(a[i][j]!='0'){
				dfs(i,j);
				count++;
			}
		}
	}
	printf("%d",count);
	return 0;
}