[dfs] 图案计数
图案计数
题目描述
一张画布里有n行*m列个格子，其中有的格子里有颜色填充，有的格子是空的没有颜色填充。现在需要你写一个程序来数出画布里边有颜色填充的格子构成了多少个图案，其中图案的定义为：
如果两个有颜色的格子边相邻或者角相邻（即横、纵两个方向上的位置差都不超过1），则他们属于同一个图案。
关于输入
第一行为两个整数n和m（1<=n, m<=200）。
之后的n行，每行为一个长度为m的字符串，构成了整个画布。字符串中，#表示颜色，-表示空白。
关于输出
一个整数，表示图案的个数
例子输入
19 48 ------------------------------------------------ ---####-----#-----#----------------------####--- --######----#-----#---------------------######-- -########--#-#---#-#####--#-##-##---#--########- -###--###--#-#---#-#----#-##-##--#--#--###--###- -###--###--#--#-#--######-#--#---#-#---###--###- -########--#--#-#--#------#--#----##---########- --######---#---#---######-#--#-----#----######-- ---####----------------------------#-----####--- ----------------------------------#------------- ------------------------------------------------ ---###--#--------#------#----------------------- --#---#-#---------------#----------------------- -#------#-##--#-##--##-###-#-##-###--###-#--##-- -#------##--#-##-#-#----#--##--#---##---##-#---- -#------#---#-#--#--#---#--#---#---##----#--#--- --#---#-#---#-#--#---#--#--#---#---##---##---#-- ---###--#---#-#--#-##---#--#---#---#-###-#-##--- ------------------------------------------------
例子输出
12
解题分析
这是一个典型的深度优先搜索（DFS）问题。在这个问题中，我们需要遍历整个画布，对每个有颜色的格子进行深度优先搜索，找出所有与其相邻的有颜色格子，并将它们标记为已访问。每次新的DFS搜索都代表一个新的图案。在实现这个算法时，我们需要注意防止对同一个格子进行多次访问。
代码实现
#include<stdio.h>#define MAX 200char grid[MAX][MAX];
int visited[MAX][MAX];
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int n, m;void dfs(int x, int y) {visited[x][y] = 1;for (int i = 0; i < 8; i++) {int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '#' && !visited[nx][ny]) {dfs(nx, ny);}}
}int main() {scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {scanf("%s", grid[i]);}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '#' && !visited[i][j]) {dfs(i, j);count++;}}}printf("%d\n", count);return 0;
}