岛屿问题

岛屿问题选编

1254. Number of Closed Islands

在LeetCode200基础上，把靠边岛屿排除即可，即先把靠边的岛屿全部淹没

public class LeetCode1254 {
    int row;
    int col;
    int[][] grid;

    public int closedIsland(int[][] grid) {
        this.row=grid.length;
        this.col=grid[0].length;
        this.grid=grid;
        int count=0;
        for (int i = 0; i < row; i++) {
            dfs(i,0);
            dfs(i,col-1);
        }
        for (int j = 0; j < col; j++) {
            dfs(0,j);
            dfs(row-1,j);
        }

        for(int i=0; i<=row-1; i++){
            for(int j=0; j<=col-1; j++){
                if(grid[i][j]==0){
                    count++;
                    dfs(i,j);
                }
            }
        }
        return count;
    }

    void dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || grid[i][j]==1){
            return;
        }
        grid[i][j]=1;
        dfs(i+1,j);
        dfs(i-1,j);
        dfs(i,j+1);
        dfs(i,j-1);
    }
}

1020. Number of Enclaves

把靠边岛屿淹没后，对不靠边的岛屿无需再dfs，直接count即可

public class LeetCode1020 {

    int row;
    int col;
    int[][] grid;
    public int numEnclaves(int[][] grid) {
        this.row=grid.length;
        this.col=grid[0].length;
        this.grid=grid;
        for (int i = 0; i < row; i++) {
            dfs(i,0);
            dfs(i,col-1);
        }
        for (int j = 0; j < col; j++) {
            dfs(0,j);
            dfs(row-1,j);
        }
        int count=0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    count++;
                }
            }
        }
        return count;
    }

    void dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || grid[i][j]==0){
            return;
        }
        grid[i][j]=0;
        dfs(i-1,j);
        dfs(i+1,j);
        dfs(i,j-1);
        dfs(i,j+1);
    }
}

695. Max Area of Island

public class LeetCode695 {
    int row;
    int col;
    int[][] grid;
    public int maxAreaOfIsland(int[][] grid) {
        this.row=grid.length;
        this.col=grid[0].length;
        this.grid=grid;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    int count=dfs(i,j);
                    max=Math.max(count,max);
                }
            }
        }
        return max==Integer.MIN_VALUE ? 0 : max;
    }

    int dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || grid[i][j]==0){
            return 0;
        }
        grid[i][j]=0;
        return 1+dfs(i-1,j)+dfs(i+1,j)+dfs(i,j-1)+dfs(i,j+1);
    }
}

1905. Count Sub Islands

先flood不可能为sub island的岛屿

public class LeetCode1905 {
    int row;
    int col;
    int[][] grid2;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        this.row=grid2.length;
        this.col=grid2[0].length;
        this.grid2=grid2;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid2[i][j]==1 && grid1[i][j]==0){
                    dfs(i,j);
                }
            }
        }
        int count=0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid2[i][j]==1){
                    count++;
                    dfs(i,j);
                }
            }
        }
        return count;
    }

    void dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || grid2[i][j]==0){
            return;
        }
        grid2[i][j]=0;
        dfs(i-1,j);
        dfs(i+1,j);
        dfs(i,j-1);
        dfs(i,j+1);
    }
}

694. Number of Distinct Islands

class Solution {
    private StringBuffer path;
    private int[][] grid;

    public int numDistinctIslands(int[][] grid) {
        this.grid = grid;
        int m = grid.length, n = grid[0].length;
        Set<String> set = new HashSet<>();
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                // 从当前点开始dfs遍历完所有相连的1的路径（1234分别表示上下左右）
                if(grid[i][j] == 1){
                    path = new StringBuffer();
                    dfs(i, j, 0);
                    set.add(path.toString());
                }
            }
        }
        return set.size();
    }
    public void dfs(int i, int j, int curr){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) return;
        grid[i][j] = 0;
        // 记录走到当前点的方式：0初始1234分别表示上下左右
        path.append(curr);
        dfs(i - 1, j, 1);
        dfs(i + 1, j, 2);
        dfs(i, j - 1, 3);
        dfs(i, j + 1, 4);
        // 每个子递归结束后(跳至上层递归前)添加相应分隔符
        path.append('|');
    }
}

463. Island Perimeter

判断四条边是否是边界

public int islandPerimeter(int[][] grid) {
    int res=0;
    int row=grid.length;
    int col=grid[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                int up;
                if(i==0){
                    up=0;
                }else{
                    up=grid[i-1][j];
                }
                int down;
                if(i==row-1){
                    down=0;
                }else{
                    down=grid[i+1][j];
                }
                int left;
                if(j==0){
                    left=0;
                }else{
                    left=grid[i][j-1];
                }
                int right;
                if(j==col-1){
                    right=0;
                }else{
                    right=grid[i][j+1];
                }
                res+=4-(up+down+left+right);
            }
        }
    }
    return res;
}

419. Battleships in a Board

public int countBattleships(char[][] board) {
    int row=board.length;
    int col=board[0].length;
    int res=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            //only the most top-left X counts
            if(board[i][j]=='X'){
                if(i>0 && board[i-1][j]=='X'){
                    continue;
                }
                if(j>0 && board[i][j-1]=='X'){
                    continue;
                }
                res++;
            }
        }
    }
    return res;
}

959. Regions Cut By Slashes

https://leetcode.com/problems/regions-cut-by-slashes/discuss/205674/DFS-on-upscaled-grid

int[][] graph;
int row;
int col;
public int regionsBySlashes(String[] grid) {
    int n=grid.length;
    graph=new int[n*3][n*3];
    row=n*3;
    col=n*3;
    for (int i = 0; i < n; i++) {
        String s=grid[i];
        for (int j = 0; j < n; j++) {
            if(s.charAt(j)=='/'){
                graph[i*3+2][j*3]=1;
                graph[i*3+1][j*3+1]=1;
                graph[i*3][j*3+2]=1;
            }else if(s.charAt(j)=='\\'){
                graph[i*3+2][j*3+2]=1;
                graph[i*3+1][j*3+1]=1;
                graph[i*3][j*3]=1;
            }
        }
    }
    int res=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(graph[i][j]==0){
                res++;
                dfs(i,j);
            }
        }
    }
    return res;
}

void dfs(int i, int j){
    if(i<0 || i>=row || j<0 || j>=col || graph[i][j]==1){
        return;
    }
    graph[i][j]=1;
    dfs(i+1,j);
    dfs(i-1,j);
    dfs(i,j+1);
    dfs(i,j-1);
}

2658. Maximum Number of Fish in a Grid

public int findMaxFish(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int res=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]!=0){
                res=Math.max(res,dfs(grid,row,col,i,j));
            }
        }
    }
    return res;
}

private int dfs(int[][] grid, int row, int col, int i, int j){
    if(i<0 || i>=row || j<0 || j>=col || grid[i][j]==0){
        return 0;
    }
    int res=grid[i][j];
    grid[i][j]=0;
    res+=dfs(grid,row,col,i+1,j);
    res+=dfs(grid,row,col,i-1,j);
    res+=dfs(grid,row,col,i,j+1);
    res+=dfs(grid,row,col,i,j-1);
    return res;
}

2852. Sum of Remoteness of All Cells

naive dfs, 超时

public long sumRemoteness(int[][] grid) {
    long res=0;
    long sum=0;
    int n= grid.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j]!=-1){
                sum+=grid[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j]!=-1){
                res+=sum;
                res-=dfs(grid,n,new boolean[n][n],i,j);
            }
        }
    }
    return res;
}

private long dfs(int[][] grid, int n, boolean[][] visited,int i, int j){
    if(i<0 || i>=n || j<0 || j>=n || grid[i][j]==-1 || visited[i][j]){
        return 0;
    }
    visited[i][j]=true;
    return grid[i][j]
            +dfs(grid,n,visited,i-1,j)
            +dfs(grid,n,visited,i+1,j)
            +dfs(grid,n,visited,i,j-1)
            +dfs(grid,n,visited,i,j+1);
}

connected subcomponent

public long sumRemoteness(int[][] grid) {
    long res=0;
    long sum=0;
    int n= grid.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j]!=-1){
                sum+=grid[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j]!=-1){

                //all nodes in this connected component:
                // total, cnt
                //then this connected component is finished!
                long[] arr=new long[2];
                dfs(grid,n,arr,i,j);
                res+=(sum-arr[0])*arr[1];
            }
        }
    }
    return res;
}

private void dfs(int[][] grid, int n, long[] res,int i, int j){
    if(i<0 || i>=n || j<0 || j>=n || grid[i][j]==-1){
        return;
    }
    res[0]+=grid[i][j];
    res[1]++;
    grid[i][j]=-1;
    dfs(grid,n,res,i+1,j);
    dfs(grid,n,res,i-1,j);
    dfs(grid,n,res,i,j-1);
    dfs(grid,n,res,i,j+1);
}