计科余定成

解题思路一：DFS（深度优先搜索）
```cpp
首先遍历整个方格图，当遇到一个黑色格子时，从该格子开始进行深度优先搜索，并将所有被搜索到的黑色格子涂成白色，表示已经被搜索过了。
在深度优先搜索的过程中，每次遇到一个黑色格子就将其上下左右的黑色格子加入搜索队列。
统计搜索的次数即可得到答案。
```
参考代码：时间复杂度:O(m*n)
```cpp
#include<bits/stdc++.h>
using namespace std;

// 定义常量N，表示方格图的最大边长
const int N = 1010;

int n, m;   // 定义方格图的尺寸n和m
int g[N][N];   // 定义存储方格图的二维数组g

int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 定义二维数组d，表示当前方向向上、下、左、右移动的偏移量

// 定义函数dfs，这个函数的功能是从当前位置(x, y)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
void dfs(int x, int y) {
	g[x][y] = 0;   // 将当前位置涂成白色

// 遍历当前位置的四周
	for (int i = 0; i < 4; i ++ ) {
		int a = x + d[i][0], b = y + d[i][1];   // 计算当前方向的位置(a, b)
		// 判断(a, b)是否越界，并且(a, b)是否为黑色格子
		if (a >= 0 && a < n && b >= 0 && b < m && g[a][b]) {
			dfs(a, b);   // 从(a, b)开始进行深度优先搜索
		}
	}
}

int main() {
	cin >> n >> m;  // 输入方格图的尺寸

// 输入方格图的具体内容
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			cin >> g[i][j];
		}
	}

int ans = 0;   // 定义变量ans，表示连通块的数量
	// 遍历整个方格图
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j]) { // 当前位置是黑色格子
				ans ++ ; // 连通块数量+1
				dfs(i, j); // 从(i, j)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
			}
		}
	}
	cout << ans << endl;  // 输出连通块的数量

return 0;
}
```

解题思路二：并查集
```cpp
我们可以将每个黑色格子看作一个节点，然后使用并查集来维护节点之间的关系。
首先，我们输入方格图的尺寸和具体内容，然后将每个节点的父节点初始化为其本身。
接下来，我们遍历整个方格图，对于每个黑色格子，我们检查其上、下、左、右四个位置是否也是黑色格子，如果是，则将这两个节点合并到同一个集合中。
最后，我们统计连通块的数量即可得到答案。
注意：在解决这道题时，我们需要注意的一个点是，当前的连通块可能不止包含一个黑色格子，因此我们在遍历方格图时，需要维护每个连通块的边界。
```
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;
int g[N][N]; // 存储方格图

int f[N * N]; // 并查集数组

// 并查集的查找函数
int find(int x) {
	if (x != f[x]) f[x] = find(f[x]);
	return f[x];
}

// 并查集的合并函数
void merge(int a, int b) {
	int ra = find(a), rb = find(b);
	if (ra == rb) return;
	f[ra] = rb;
}
int main() {
	cin >> n >> m;

// 输入方格图
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			cin >> g[i][j];
		}
	}

// 初始化每个连通块的父节点
	for (int i = 0; i < n * m; i ++ ) f[i] = i;

// 枚举每个位置，如果是黑色格子则检查其上、下、左、右四个位置是否也是黑色格子，如果是则合并
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j]) {
				if (i && g[i - 1][j]) merge(i * m + j, (i - 1) * m + j);
				if (j && g[i][j - 1]) merge(i * m + j, i * m + j - 1);
			}
		}
	}

int ans = 0;
	// 枚举每个位置，如果是黑色格子且是它所在连通块的根节点，则答案加1
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j] && f[i * m + j] == i * m + j) ans ++ ;
		}
	}

cout << ans << endl;

return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

连通块（并查集和DFS做法）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

求圆的面积（C语言代码）

幸运数（C++代码）

1012题解

A+B for Input-Output Practice (IV) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

Tom数（C语言代码）

C二级辅导-进制转换（C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

连通块（并查集和DFS做法）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

求圆的面积 （C语言代码）

幸运数 （C++代码）

1012题解

A+B for Input-Output Practice (IV) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

Tom数 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

求圆的面积（C语言代码）

幸运数（C++代码）

Tom数（C语言代码）

C二级辅导-进制转换（C语言代码）