输入一个n乘m的矩阵,1代表海洋,0代表陆地,四周相邻的陆地属于同一座岛屿,求一共有多少座岛屿
时间: 2024-03-18 16:39:20 浏览: 22
好的,我明白了你的问题。这是一个典型的图论问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)进行解决。
以下是使用DFS解决这个问题的步骤:
1. 遍历整个矩阵,当遇到值为0的陆地时,从该点开始进行DFS搜索。
2. 在DFS搜索过程中,将所有与当前节点相邻的陆地(上下左右四个方向)标记为已访问,并将它们加入到同一个岛屿中。
3. 当DFS搜索结束时,即当前岛屿中所有相邻的陆地都已经被标记为已访问时,计数器加1,表示发现了一座新的岛屿。
4. 重复1-3的过程,直到遍历完整个矩阵,统计出总共有多少座岛屿。
代码实现如下(假设矩阵为mat,n为行数,m为列数):
```
int countIslands(vector<vector<int>> mat, int n, int m) {
int count = 0;
vector<vector<bool>> visited(n, vector<bool>(m, false)); // 记录每个点是否已经被访问过
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && mat[i][j] == 0) { // 如果当前点未访问过且为陆地
count++; // 岛屿数加1
dfs(mat, visited, i, j, n, m); // 对当前岛屿进行DFS搜索
}
}
}
return count;
}
void dfs(vector<vector<int>> mat, vector<vector<bool>>& visited, int i, int j, int n, int m) {
if (i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || mat[i][j] == 1) {
// 当前点越界、已访问过或为海洋,直接返回
return;
}
visited[i][j] = true; // 标记当前点为已访问
dfs(mat, visited, i-1, j, n, m); // 上方
dfs(mat, visited, i+1, j, n, m); // 下方
dfs(mat, visited, i, j-1, n, m); // 左方
dfs(mat, visited, i, j+1, n, m); // 右方
}
```
这样就可以求出给定矩阵中一共有多少座岛屿了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)