微信网站模板免费下载,建一个网站的手机电脑,Wordpress 帖子翻译,网站建设期末考试这几天复习的搜索把之前做过的题目看了一下。 解析#xff1a;int dx[5]{0,0,1,0,-1}; 和 int dy[5]{0,1,0,-1,0};#xff1a;这两个数组用于表示上下左右四个方向的偏移量#xff0c;方便在 DFS 中访问相邻的元素。o 和 p 分别表示当前搜索位置的行和列。边界条件判断…这几天复习的搜索把之前做过的题目看了一下。 解析int dx[5]{0,0,1,0,-1}; 和 int dy[5]{0,1,0,-1,0};这两个数组用于表示上下左右四个方向的偏移量方便在 DFS 中访问相邻的元素。o 和 p 分别表示当前搜索位置的行和列。边界条件判断如果当前位置超出矩阵范围o0||on1||p0||pn1或者当前位置的值不为 0则直接返回。标记当前位置将当前位置的值标记为 1表示该位置已经被访问过。递归搜索相邻位置通过 dx 和 dy 数组遍历当前位置的上下左右四个相邻位置并递归调用 dfs 函数进行搜索。首先读取矩阵的大小 n然后使用双重循环读取 n x n 的矩阵元素并将其存储在数组 a 中同时将 a 中的元素复制到数组 b 中。从边界开始进行深度优先搜索分别从矩阵的上下左右边界开始调用 dfs 函数进行搜索将与边界相连的所有 0 标记为 1。替换未标记的 0遍历数组 a如果某个位置的值仍然为 0说明该位置被 1 完全包围将数组 b 中对应位置的值替换为 2。 输出结果使用双重循环遍历数组 b并输出处理后的矩阵。
#includestdio.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(o0||on1||p0||pn1||a[o][p]!0){return;}a[o][p]1;for(i1;i4;i){dfs(odx[i],pdy[i]);}
}int main()
{int i,j;scanf(%d,n);for(i0;in;i){for(j0;jn;j){scanf(%d,a[i][j]);b[i][j]a[i][j];}}for(i0;in;i)dfs(0,i);for(i0;in;i)dfs(n-1,i);for(i0;in;i)dfs(i,0);for(i0;in;i)dfs(i,n-1);for(i0;in;i){for(j0;jn;j){if(a[i][j]0)b[i][j]2;}}for(i0;in;i){for(j0;jn;j)printf(%d ,b[i][j]);printf(\n);}return 0;
} 解析使用双重循环遍历整个二维网格。当遇到字符不为 0 的位置时调用 dfs 函数进行深度优先搜索将该连通区域的所有 1 标记为 0。每完成一次 dfs 搜索就意味着找到了一个新的连通区域count 加 1。
#includestdio.h
int n,m,count0;
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(x1||xn||y1||ym||a[x][y]0)return;a[x][y]0;for(i1;i4;i){dfs(xdx[i],ydy[i]);}
}int main()
{int i,j;scanf(%d %d,n,m);for(i1; in; i) {for(j1; jm; j) {scanf( %c,a[i][j]);}}for(i1; in; i) {for(j1; jm; j) {if(a[i][j]!0){dfs(i,j);count;}}}printf(%d,count);return 0;
}
