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 0
        m = len(grid)
        n = len(grid[0])
        #visited = set()
        count = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    helper(i,j)
                    count += 1
        return 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 0
        n, m = len(grid), len(grid[0])
        
        #Union Find
        roots = {(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 p
        def 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))