一站式营销型网站建设服务,如何自己做公司网页,网站开发php未来发展,离职模板网输入一个n*n的黑白图像#xff08;1表示黑色#xff0c;0表示白色#xff09;#xff0c;任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点#xff0c;就说它们属于同一个八连块。如图6-11所示的图形有3个八连块。 图6-11 拥有3个八连块的黑白图形 【分析…输入一个n*n的黑白图像1表示黑色0表示白色任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点就说它们属于同一个八连块。如图6-11所示的图形有3个八连块。 图6-11 拥有3个八连块的黑白图形 【分析】 用递归求解从每个黑格子出发递归访问它所有的相邻黑格。 int mat[MAXN][MAXN], vis[MAXN][MAXN];
void dfs(int x, int y) {if(!mat[x][y] || vis[x][y]) return; // 曾经访问过这个格子或者当前格子是白色vis[x][y] 1; // 标记(x,y)已访问过dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y1);dfs(x-1,y); dfs(x,y1);dfs(x1,y-1); dfs(x1,y); dfs(x1,y1); // 递归访问周围的八个格子
}
这里黑格(x,y)的mat[x][y]为1白格为0。为了避免同一个格子访问多次用标志vis[x][y]记录格子(x,y)是否访问过。在输入之前在迷宫的外面加上一圈虚拟的白格子见下面的程序。
memset(mat, 0, sizeof(mat)); //所有格子都初始化为白色,包括周围一圈的虚拟格子
memset(vis, 0, sizeof(vis)); // 所有格子都没有访问过
scanf(%d, n);
for(int i 0; i n; i) {scanf(%s, s);for(int j 0; j n; j)mat[i1][j1] s[j]-0; // 把图像往中间移动一点空出一圈白格子
}接下来只需不断找黑格然后调用dfs。从它出发寻找八连块 int count 0;
for(int i 1; i n; i)for(int j 1; j n; j)if(!vis[i][j] mat[i][j]) { count; dfs(i,j); }
//找到没有访问过的黑格
printf(%d\n, count);完整的程序如下 #include stdio.h
#include string.h
const int MAXN 1000;
int n;int mat[MAXN][MAXN], vis[MAXN][MAXN];
void dfs(int x, int y) {if(!mat[x][y] || vis[x][y]) return; //曾经访问过这个格子或者当前
格子是白色
vis[x][y] 1; // 标记(x,y)已访问过dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y1);dfs(x-1,y); dfs(x,y1);dfs(x1,y-1); dfs(x1,y); dfs(x1,y1); // 递归访问周围的八个格子
}int main() {char s[MAXN 10];memset(mat, 0, sizeof(mat)); // 所有格子都初始化为白色包括周围
一圈的虚拟格子memset(vis, 0, sizeof(vis)); // 所有格子都没有访问过scanf(%d, n);for(int i 0; i n; i) {scanf(%s, s);for(int j 0; j n; j)mat[i1][j1] s[j]-0; // 把图像往中间移动一点空出一圈白格子}int count 0;for(int i 1; i n; i)for(int j 1; j n; j)// 找到没有访问过的黑格if(!vis[i][j] mat[i][j]) { count; dfs(i,j); } printf(%d\n, count);return 0;
}上面的函数dfs就是深度优先遍历Depth-FirstSearchDFS的算法DFS和BFS一样都是从一个结点出发按照某种特定的次序访问图中的其他特点。不同的是BFS使用队列来存放待扩展结点而DFS使用的是栈。 附我自己理解后敲的代码 #include stdio.h
#include string.h
#includealgorithm
#includeiostream
#define M 1020
using namespace std;
int n;
int i,j;
char map[M][M];
void dfs(int x,int y)
{if(map[x][y]!1||x0||y0||xn||yn)return; //曾经访问过这个格子或者当前格子是白色else{map[x][y] 0; // 标记(x,y)已访问过dfs(x-1,y-1);dfs(x-1,y1);dfs(x-1,y);dfs(x,y1);dfs(x,y-1);dfs(x1,y-1);dfs(x1,y);dfs(x1,y1); // 递归访问周围的八个格子}
}int main()
{memset(map, 0, sizeof(map)); // 所有格子都没有访问过scanf(%d, n);for(i0; in; i)for(j0; jn; j)cinmap[i][j];int count 0;for(i 0; i n; i)for(j 0; j n; j){// 找到没有访问过的黑格if(map[i][j]1){dfs(i,j);count;}}printf(%d\n, count);return 0;
}
/*
6
100100
001010
000000
110000
111000
010100
*/转载于:https://www.cnblogs.com/dyllove98/p/3226233.html