讨论/《深度优先搜索》 - 练习:岛屿数量/
《深度优先搜索》 - 练习:岛屿数量
共 3 个回复

class Solution {

private int row;
private int col;
private char[][] grid;
private int[][] directions = {{-1,0},{1,0},{0,1},{0,-1}};
public int numIslands(char[][] grid) {
    if(grid ==null||grid.length==0){
        return 0;
    }
    this.row = grid.length;
    this.col = grid[0].length;
    this.grid = grid;
    int res = 0;
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            if(grid[i][j]=='1'){
                res++;
                dfs(i,j);
            }
        }
    }
    return res;
}
public void dfs(int i,int j){
    if(i<0||j<0||i>=row||j>=col||grid[i][j]=='0'){
        return;
    }
    grid[i][j]='0';
    for(int[]direction:directions){
        int x = i+direction[0];
        int y = j+direction[1];
        dfs(x,y);
    }
}

}

class Solution {
public:
    
    void dfs(vector<vector<char>>& grid, int i, int j, int m, int n){
        if( (i<0 || i>=m) || (j<0 || j>=n) || grid[i][j]=='0')
            return;
        
        //other wise do dfs
        grid[i][j]='0'; //mark it as water
        dfs(grid, i-1, j, m, n);
        dfs(grid, i, j+1, m, n);
        dfs(grid, i+1, j, m, n);
        dfs(grid, i, j-1, m, n);
    }
    
    
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size();
        int count=0;
        int n=grid[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='1'){
                    count++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return count;
    }
};
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        p = {}
        cnt = 0
        def find(x):
            p.setdefault(x, x)
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        def union(x, y):
            nonlocal cnt
            if find(x) != find(y): 
                p[find(x)] = find(y)
                cnt -= 1
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    cnt += 1
                    for x, y in [[-1, 0], [0, -1]]:
                        Ti = i + x
                        Tj = j + y
                        if 0 <= Ti <row and 0 <= Tj <col and grid[Ti][Tj]== "1":
                            union(Ti * col + Tj, i * col + j)
        return cnt