题目要求
找出所有的细胞块。
辅助题目:
- 1\sim9 为细胞。
- 上下左右还是细胞为同一个细胞(简称细胞块)。
题目大意到此为止。
题目思路
利用 dfs 深度优先搜索算法(洪水填充)做出来。
我们要 for 循环将每个位置全部看一遍,如果 a_{ij} 为细胞( 0\sim9 )与这个位置没走过(因为没走过所以要走)( vis=0 ),我们要将计算细胞块的变量加一(此操作为了计数),则我们可以将这一整块细胞全部标上 vis=1 ,这样就不会判重,下次再判断到细胞的时候就会因为走过( vis=1 )而不重复加。
简单说成:因为上下左右都是细胞为细胞块,所以只有遇到细胞快的其中一个细胞就将整块细胞的 vis 全部标上 1 ,这样就不会重复判断了。
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='0'&&vis[i][j]==0){
dfs(i,j);ans++;
}
}
}
接下来是 dfs 部分:
因为是上下左右四个方向,所以 dx,dy 定义大小为 4 ,里面的数字看心情。
为什么看心情?
因为:搜索 4 个方向是枚举,所以要将每个方向全部枚举到,既然是每个方向( 4 个方向)都要枚举到,所以先后顺序无所谓。
接下来是灵魂三连问:
不要背模板,要理解。
首先是边界,边界超了枚举什么啊?枚举不存在的东西?所以要判断边界。
if(xx<1||yy<1||xx>n||yy>m)continue;
然后是走没走过,既然走过了那么 vis 就标了 1 不用重复走,重点是走过了和复杂度问题。
if(vis[xx][yy]==1)continue;
最后是不能走,在以前学过的经典题目中这个是墙,不能走,而在这里是不是细胞,因为要标细胞,所以不是细胞不用标。
if(a[xx][yy]=='0')continue;
既然所有不能标的情况都说完了,那么剩下的就是可以标的。将 vis_{i,j} 标位 1 就行。
最后递归下一个地方。
整体代码
思路讲完了,接下来是整体代码:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int vis[105][105];
char a[105][105];
int n,m,ans=0;
void dfs(int x,int y){
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(vis[xx][yy]==1)continue;
if(xx<1||yy<1||xx>n||yy>m)continue;
if(a[xx][yy]=='0')continue;
vis[xx][yy]=1;
dfs(xx,yy);
}
}