染色问题例题讲解

题目要求

找出所有的细胞块。

辅助题目:

  • 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);
	}
}

3 个赞

有点蒙,私聊讲?不过写的确实好啊

1 个赞