东营网站设计公司,农产品线上推广方案,央视网新闻,餐饮小程序开发1329#xff1a;【例8.2】细胞
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一矩形阵列由数字0 到9组成,数字1到9 代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 4 10 0234500067 1034560500 2045600671 00000000…1329【例8.2】细胞
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一矩形阵列由数字0 到9组成,数字1到9 代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 4 10 0234500067 1034560500 2045600671 0000000089 有4个细胞。
【输入】 第一行为矩阵的行n和列m; 下面为一个n×m的矩阵。 【输出】 细胞个数。
【输入样例】 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】 4
解析 题意可知只要是上下左右相邻都是不为0数字即为同一种细胞我第一次读以为只有上下左右有数字不为0才能算一种细胞emmmm傻狗
如果把该二位数组每个位置视为节点则题目思路如下 可以用深度优先算法从第一个节点开始遍历然后分别判断其上下左右是否有相邻的。dfs的精髓就是每次再判断这个节点的数的‘邻居’是否其相邻是同一细胞时只要是就立即dfs该‘邻居’,继续dfs直到判断完成又回溯到上一个节点判断其上下左右。 也可以用广度优先算法从一个节点开始遍历然后分别判断其上下左右是否是同一种细胞如果是则上下左右判断完后再判断该节点的上下左右即该节点的上面一个节点 而表示这个遍历了上下左右后再回到该节点就需要用到队列先进先出可以用一个结构体队列将下标(x,y遍历时入队然后判断四个方向如果是同一种细胞则压入队列四个方向遍历完后回到队列头部将其出队q.pop(),然后又从队头开始去判断其四个方向直到该队列为空说明这一种细胞已经搜索完了由于队列的顺序性也可以不用结构体数组直接分别将x,y分别压入队列在获取到队头的x后及时Pop也可以通过q.front()拿到y,所以可以不用结构体数组 不管是哪个搜索都可以在搜索到一个节点时及时标注用一个数组去记录是否访问过减少遍历时间。由于此题特殊可以直接将数组值设为0,也可以在搜索完成后不会出现二次遍历的情况
代码示例
深度优先搜索
//深搜-样例比较小时可以用
#includebits/stdc.h
using namespace std;
#define N 101
int n,m,num;
char a[N][N];
int dx[4]{-1,1,0,0}; //上、下、左、右四个方向
int dy[4]{0,0,-1,1};
void dfs(int x,int y);
int main()
{cinnm; for(int i0;in;i)scanf(%s,a[i]);//遍历每个元素用标记数组标记已经访问过的则可以避免二次遍历 减缩短运行时间 for(int i0;in;i){for(int j0;jm;j){if(a[i][j]!0){num; //没被访问过说明是新的不同的细胞 dfs(i,j); //搜索这一元素的四个方向}}}coutnum;return 0;
}
void dfs(int x,int y)
{a[x][y]0;//为0即也表示该细胞已经访问过了 int newx,newy;for(int i0;i4;i){newxxdx[i];newyydy[i];//首先保证在边界内其次保证他是细胞最后保证他是未被访问过的 都满足即可继续访问其周围的细胞 if(newxn newx0 newym newy0a[newx][newy]!0) {dfs(newx,newy);}}
}广度优先搜索
//广搜
#includebits/stdc.h
using namespace std;
#define N 101
int n,m,num;
char a[N][N];
int dx[4]{-1,1,0,0}; //上、下、左、右四个方向
int dy[4]{0,0,-1,1};
queueintq;//数据类型为int的队列 -先进先出
void bfs(int x,int y);
int main()
{cinnm; for(int i0;in;i)scanf(%s,a[i]);for(int i0;in;i){for(int j0;jm;j){if(a[i][j]!0){num; //没被访问过说明是新的不同的细胞 bfs(i,j); //搜索这一元素的四个方向}}}coutnum;return 0;
}
void bfs(int x,int y)
{a[x][y]0;//表示访问过 ,在这里不会影响入队后的周围细胞的判断因为一次bfs就完成了同一个细胞的问题 q.push(x),q.push(y);//将下标分别压入队列属于同一个细胞队列 int newx,newy;//同一个细胞队列先拿到队列的数据出队处理然后一次访问四个方向(立即出队便于后面同一种细胞进来保证每次循环处理的是新一个细胞) while(!q.empty()){int nxq.front(); q.pop();int nyq.front();q.pop();for(int i0;i4;i){newxnxdx[i],newy nydy[i];if(newxn newx0 newym newy0a[newx][newy]!0) {//继续压入栈是同一个细胞q.push(newx);q.push(newy);a[newx][newy]0;//只是压入同一个细胞的栈不会继续搜索所以要标记为以访问避免重复访问 }}} }深度优先算法BFS是一种图像搜索演算法属于一种盲目搜寻法目的是系统地展开并检查图中的所有节点主要借助一个队列、一个布尔类型数组、邻接矩阵完成**。
从图像来看他是先一个节点搜索所有的子节点遍历完毕后再回到同层次的第一个的节点再次遍历其所有子节点。
在实际运用时遍历子节点的过程实质是求完一个情况的所有相邻的解再开始搜索下一个节点以下是bfs和dfs的树遍历对比
