免费建微网站平台,品牌建设方式有哪些,我需要把网站做,如何设计网站首页导航图案计数
题目描述
一张画布里有n行*m列个格子#xff0c;其中有的格子里有颜色填充#xff0c;有的格子是空的没有颜色填充。现在需要你写一个程序来数出画布里边有颜色填充的格子构成了多少个图案#xff0c;其中图案的定义为#xff1a; 如果两个有颜色的格子边相邻或…图案计数
题目描述
一张画布里有n行*m列个格子其中有的格子里有颜色填充有的格子是空的没有颜色填充。现在需要你写一个程序来数出画布里边有颜色填充的格子构成了多少个图案其中图案的定义为 如果两个有颜色的格子边相邻或者角相邻即横、纵两个方向上的位置差都不超过1则他们属于同一个图案。
关于输入
第一行为两个整数n和m1n, m200。 之后的n行每行为一个长度为m的字符串构成了整个画布。字符串中#表示颜色-表示空白。
关于输出
一个整数表示图案的个数
例子输入
19 48
------------------------------------------------
---####-----#-----#----------------------####---
--######----#-----#---------------------######--
-########--#-#---#-#####--#-##-##---#--########-
-###--###--#-#---#-#----#-##-##--#--#--###--###-
-###--###--#--#-#--######-#--#---#-#---###--###-
-########--#--#-#--#------#--#----##---########-
--######---#---#---######-#--#-----#----######--
---####----------------------------#-----####---
----------------------------------#-------------
------------------------------------------------
---###--#--------#------#-----------------------
--#---#-#---------------#-----------------------
-#------#-##--#-##--##-###-#-##-###--###-#--##--
-#------##--#-##-#-#----#--##--#---##---##-#----
-#------#---#-#--#--#---#--#---#---##----#--#---
--#---#-#---#-#--#---#--#--#---#---##---##---#--
---###--#---#-#--#-##---#--#---#---#-###-#-##---
------------------------------------------------
例子输出
12
解题分析
这是一个典型的深度优先搜索DFS问题。在这个问题中我们需要遍历整个画布对每个有颜色的格子进行深度优先搜索找出所有与其相邻的有颜色格子并将它们标记为已访问。每次新的DFS搜索都代表一个新的图案。在实现这个算法时我们需要注意防止对同一个格子进行多次访问。
代码实现
#includestdio.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;
}
