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,直到判断完成,又回溯到上一个节点,判断其上下左右。
也可以用广度优先算法:从一个节点开始遍历,然后分别判断其上下左右是否是同一种细胞,如果是,则上下左右判断完后,再判断该节点的上下左右(即该节点的上面一个节点)
q.pop()
),然后又从队头开始去判断其四个方向,,,,直到该队列为空,说明这一种细胞已经搜索完了(由于队列的顺序性,也可以不用结构体数组,直接分别将x,y分别压入队列,在获取到队头的x后,及时Pop
(),也可以通过q.front()
拿到y,所以可以不用结构体数组)不管是哪个搜索,都可以在搜索到一个节点时,及时标注(用一个数组去记录是否访问过),减少遍历时间。由于此题特殊,可以直接将数组值设为0,也可以在搜索完成后不会出现二次遍历的情况
代码示例:
深度优先搜索
//深搜-样例比较小时可以用
#include<bits/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()
{
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%s",&a[i]);
//遍历每个元素,用标记数组标记已经访问过的,则可以避免二次遍历 ,减缩短运行时间
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]!='0')
{
num++; //没被访问过说明是新的不同的细胞
dfs(i,j); //搜索这一元素的四个方向
}
}
}
cout<<num;
return 0;
}
void dfs(int x,int y)
{
a[x][y]='0';//为0即也表示该细胞已经访问过了
int newx,newy;
for(int i=0;i<4;i++)
{
newx=x+dx[i];
newy=y+dy[i];
//首先保证在边界内,其次保证他是细胞,最后保证他是未被访问过的 ,都满足即可继续访问其周围的细胞
if(newx<n && newx>=0 && newy<m && newy>=0&&a[newx][newy]!='0')
{
dfs(newx,newy);
}
}
}
广度优先搜索
//广搜
#include<bits/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};
queue<int>q;//数据类型为int的队列 -先进先出
void bfs(int x,int y);
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%s",&a[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]!='0')
{
num++; //没被访问过说明是新的不同的细胞
bfs(i,j); //搜索这一元素的四个方向
}
}
}
cout<<num;
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 nx=q.front();
q.pop();
int ny=q.front();
q.pop();
for(int i=0;i<4;i++){
newx=nx+dx[i],newy= ny+dy[i];
if(newx<n && newx>=0 && newy<m && newy>=0&&a[newx][newy]!='0') {
//继续压入栈(是同一个细胞)
q.push(newx);
q.push(newy);
a[newx][newy]='0';//只是压入同一个细胞的栈,不会继续搜索,所以要标记为以访问,避免重复访问
}
}
}
}
深度优先算法BFS是一种图像搜索演算法,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,主要借助一个队列、一个布尔类型数组、邻接矩阵完成**。
从图像来看,他是先一个节点搜索所有的子节点遍历完毕后,再回到同层次的第一个的节点再次遍历其所有子节点。
在实际运用时,遍历子节点的过程实质是求完一个情况的所有相邻的解,再开始搜索下一个节点
以下是bfs和dfs的树遍历对比