Leetcode 200. Number of Islands (python+cpp)

题目

解法1：DFS

每次遇到1时进行dfs，并将访问到连在一起的1都进行mark。总共进行DFS的次数就是island的个数
python代码：

class Solution:def numIslands(self, grid: List[List[str]]) -> int:def helper(i,j):if i<0 or i>=m or j<0 or j>=n or grid[i][j]!='1':return#visited.add((i,j))grid[i][j] = '0'helper(i+1,j)helper(i-1,j)helper(i,j-1)helper(i,j+1)if not grid or not grid[0]:return 0m = len(grid)n = len(grid[0])#visited = set()count = 0for i in range(m):for j in range(n):if grid[i][j] == '1':helper(i,j)count += 1return count

C++版本：

class Solution {
    
public:int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;int m = grid.size();int n = grid[0].size();int count = 0;for (int i=0;i<m;i++){
    for (int j=0;j<n;j++){
    if (grid[i][j] == '1'){
    count++;grid[i][j] = '0';queue<pair<int,int>> q;q.push({
    i,j});vector<pair<int,int>> dirs{
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};while (!q.empty()){
    auto curr = q.front();q.pop();for (auto d:dirs){
    int x = d.first + curr.first;int y = d.second + curr.second;if (x>=0 and y>=0 and x<m and y<n && grid[x][y]=='1'){
    q.push({
    x,y});grid[x][y] = '0';}}}}}}return count;}
};

解法2：union find

利用union find将所有的连在一起的1的位置归到一个root，最后一共有多少个root就有多少个岛。值得注意的是，与DFS或者BFS的方法不同的是，不需要搜索四个方向，只需要看两个方向即可

class Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid or not grid[0]: return 0n, m = len(grid), len(grid[0])#Union Findroots = {
    (y, x):(y, x) for y in range(n) for x in range(m) if grid[y][x] == "1"}def find(p):while p != roots[p]:p = roots[p]return pdef union(p,q):roots[find(p)] = find(q)for y in range(n):for x in range(m):if grid[y][x] == "1":if x+1 < m and grid[y][x+1] == "1": union((y,x),(y,x+1))if y+1 < n and grid[y+1][x] == "1": union((y,x),(y+1,x))return len(set(find(roots[(y, x)]) for (y, x) in roots))