用C++实现上述要求
时间: 2024-10-17 15:09:49 浏览: 20
juanji.rar_c++实现卷积
在C++中,你可以使用`std::vector<bool>`来表示矩阵,并利用深度优先搜索(DFS)来找到每个区域。以下是一个简单的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <stack>
// 用于存储网格的结构体
struct Grid {
std::vector<std::vector<bool>> grid;
std::vector<int> visited; // 记录访问状态
};
int dfs(const Grid& g, int i, int j, int& region) {
g.visited[i][j] = true;
region++;
// 四邻域检查
if (i > 0 && !g.visited[i - 1][j]) dfs(g, i - 1, j, region);
if (i < g.grid.size() - 1 && !g.visited[i + 1][j]) dfs(g, i + 1, j, region);
if (j > 0 && !g.visited[i][j - 1]) dfs(g, i, j - 1, region);
if (j < g.grid[0].size() - 1 && !g.visited[i][j + 1]) dfs(g, i, j + 1, region);
return region;
}
int countRegions(const Grid& g) {
int region = 0;
for (int i = 0; i < g.grid.size(); ++i)
for (int j = 0; j < g.grid[i].size(); ++j)
if (!g.visited[i][j] && g.grid[i][j])
region = dfs(g, i, j, region);
return region;
}
int main() {
int n, m;
std::cin >> n >> m;
Grid grid(n, m);
grid.grid.resize(n);
for (int i = 0; i < n; ++i) {
grid.grid[i].resize(m);
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
grid.grid[i][j] = c == '1';
}
}
int regions = countRegions(grid);
std::cout << "Region count: " << regions << std::endl;
return 0;
}
```
在这个代码里,我们首先读取输入矩阵,然后遍历每个元素进行DFS。每次遇到新的1(表示有东西),就在当前区域加一,并对其周边进行递归检查。最后返回总的区域数。
注意这只是一个基本版本,实际应用中你可能还需要考虑内存管理和其他边界条件处理。同时,C++标准库可能不包含`std::vector<bool>`,你可以选择使用`bool`数组替代。
阅读全文