岛屿问题刷题

200. 岛屿数量 - 力扣（LeetCode）

class Solution {
    public int numIslands(char[][] grid) {
        int n = grid.length;//grid行数
        int m = grid[0].length;//grid列数
        int res = 0;
        for(int r = 0;r<n;r++){
            for(int c=0;c<m;c++){
                if(grid[r][c]=='1'){
                    dfs(grid,r,c);
                    res++;
                }
            }
        }
        return res;    
    }

    public void dfs(char[][] grid,int r,int c){
        if(!inArea(grid,r,c)){
            return;
        }
        if(grid[r][c]!='1'){
            return;
        }
        grid[r][c] = '2';

        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
        dfs(grid,r,c+1);
        dfs(grid,r,c-1);
    }

    public boolean inArea(char[][] grid,int r,int c){
        return r>=0&&r<grid.length&&c>=0&&c<grid[0].length;
    }

}

463. 岛屿的周长 - 力扣（LeetCode）

class Solution {
    public int islandPerimeter(int[][] grid) {
        for(int r = 0;r<grid.length;r++){
            for(int c = 0;c<grid[0].length;c++){
                if(grid[r][c] == 1){
                    //题目说只有一个
                    return dfs(grid,r,c);
                }
            }
        }
        return 0;
    }

    int dfs(int[][] grid,int r,int c){
        //函数因为坐标(r,c)超出网格范围,返回对应一条黄色的边
        if(!inArea(grid,r,c)){
            return 1;
        }
        //函数因为[当前格子是海洋格子]返回,对应一条蓝色的边
        if(grid[r][c]==0){
            return 1;
        }
        //函数因为[当前格子已经是遍历的陆地格子]返回,跟周长没有关系
        if(grid[r][c]!=1){
            return 0;
        }
        grid[r][c] = 2;
        return dfs(grid,r-1,c)+dfs(grid,r+1,c)
        +dfs(grid,r,c-1)+dfs(grid,r,c+1);
    }
    //判断[r,c]是否在网络中
    boolean inArea(int[][] grid,int r,int c){
        return 0<=r&&r<grid.length&&0<=c&&c<grid[0].length;
    }
}

695. 岛屿的最大面积 - 力扣（LeetCode）

class Solution {
    public int[] dx = {0,0,1,-1};
    public int[] dy = {1,-1,0,0};
    public int row,col;
    public boolean[][] check = new boolean[50][50];
    public int count = 0;
    public int ret = 0;
    public int maxAreaOfIsland(int[][] grid) {
       row = grid.length;
       col = grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(!check[i][j] && grid[i][j] ==1){
                    count=0;//重置count
                    dfs(grid,i,j);
                    ret = Integer.max(ret,count);
                }
            }
        }
        return ret;
    }
    private void dfs(int[][] grid,int i,int j){
        count++;
        check[i][j] = true;
        for(int k=0;k<4;k++){
            int x = i+dx[k],y = j+dy[k];
            if(x>=0&&x<row&&y>=0&&y<col&&!check[x][y]&&grid[x][y]==1){
                dfs(grid,x,y);
            }
        }

    }
}

827. 最大人工岛 - 力扣（LeetCode）

class Solution {
    public int largestIsland(int[][] grid) {
        // dfs+哈希表

        //算法: 对所有岛屿编号,再遍历所有0,枚举所有能相连的岛屿的面积和最大值
        int n = grid.length;
        int maxArea = 0,islandIdx = 2;

        //1.对所有岛屿编号并记录在哈希表中
        Map<Integer,Integer>map = new HashMap<>();// key-岛屿编号 value-岛屿面积
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j] == 1){
                    int area = dfs(grid,i,j,islandIdx);
                    map.put(islandIdx,area);
                    islandIdx++;
                    maxArea = Math.max(area,maxArea);
                }
            }
        }
        //2.枚举所有0的上下左右可能连接的情况
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                Set<Integer>set = new HashSet<>();//记录/区分当前0周围的不同岛屿
                if(grid[i][j] == 0){
                    //如果相邻的格子,没越界,且是岛屿,则把[岛屿编号]加入set
                    if(i-1>=0&&grid[i-1][j] >= 2){
                        set.add(grid[i-1][j]);//上
                    }
                    if(i+1<n&&grid[i+1][j]>=2){
                        set.add(grid[i+1][j]);//下
                    }
                    if(j-1>=0&&grid[i][j-1]>=2){
                        set.add(grid[i][j-1]);//左
                    }
                    if(j+1<n&&grid[i][j+1]>=2){
                        set.add(grid[i][j+1]);//右
                    }

                    //初始化当前连接后的最大面积和
                    int curMaxArea = 1;//
                    for(int idx:set){
                        int otherArea = map.get(idx);
                        curMaxArea+=otherArea;
                    }
                    maxArea = Math.max(maxArea,curMaxArea);
                }
            }
        }
        return maxArea;
    }

    int dfs(int[][] grid,int x,int y,int islandIdx){
        //递归终止条件
        if(x<0||x>=grid.length||y<0||y>=grid[0].length||grid[x][y]!=1){
            return 0;
        }
        //标记已访问
        grid[x][y] = islandIdx;
        return 1+dfs(grid,x+1,y,islandIdx)
        +dfs(grid,x-1,y,islandIdx)
        +dfs(grid,x,y+1,islandIdx)
        +dfs(grid,x,y-1,islandIdx);
    }
}