岛屿数量问题

        给一个0 1矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

 C++ 解决方案

#include <iostream>
#include <vector>using namespace std;void dfs(vector<vector<int>>& grid, int i, int j) {if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {return;}grid[i][j] = 0; // Mark the current cell as visited// Visit all four adjacent cellsdfs(grid, i - 1, j); // Updfs(grid, i + 1, j); // Downdfs(grid, i, j - 1); // Leftdfs(grid, i, j + 1); // Right
}int numIslands(vector<vector<int>>& grid) {int count = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) {++count;dfs(grid, i, j); // Start DFS from the current cell to mark all connected 1s as visited}}}return count;
}int main() {vector<vector<int>> grid = {{1, 1, 0, 0, 0},{1, 1, 0, 0, 1},{0, 0, 1, 0, 1},{0, 0, 0, 1, 1}};cout << "Number of islands: " << numIslands(grid) << endl;return 0;
}

Python 解决方案 

def dfs(grid, i, j):if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:returngrid[i][j] = 0  # Mark the current cell as visited# Visit all four adjacent cellsdfs(grid, i - 1, j)  # Updfs(grid, i + 1, j)  # Downdfs(grid, i, j - 1)  # Leftdfs(grid, i, j + 1)  # Rightdef num_islands(grid):count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:count += 1dfs(grid, i, j)  # Start DFS from the current cell to mark all connected 1s as visitedreturn count# Example usage
grid = [[1, 1, 0, 0, 0],[1, 1, 0, 0, 1],[0, 0, 1, 0, 1],[0, 0, 0, 1, 1]
]print("Number of islands:", num_islands(grid))

解释

1. 深度优先搜索（DFS）：
   • dfs函数用于遍历所有与当前陆地相连的陆地，并将它们标记为已访问（即0）。
   • 每当遇到一个未访问的陆地（即值为1的单元格），我们增加岛屿计数，并调用dfs来标记所有相连的陆地。
2. 遍历矩阵：
   • numIslands函数遍历整个矩阵，每当遇到一个新的陆地时，调用dfs函数，并增加岛屿计数。

复杂度

• 时间复杂度：O(M * N)，其中M是矩阵的行数，N是矩阵的列数，因为我们需要遍历整个矩阵一次。
• 空间复杂度：O(M * N)（在极端情况下，递归调用栈的深度可能达到这个级别），但由于DFS的深度通常较小，实际空间占用可能会更小。