最大的陆地面积

给定一个0-1矩阵求最大的陆地面积，1的连通块

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    res=Math.max(res,dfs(grid,i,j));
                }
            }
        }
        return res;
    }
    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};
    public int dfs(int[][] grid,int i,int j){
        int res=1;
        grid[i][j]=0;
        for(int k=0;k<4;k++){
            int a=i+dx[k];
            int b=j+dy[k];
            if(a<0||a>=grid.length||b<0||b>=grid[0].length||grid[a][b]==0){
                continue;
            }
            res+=dfs(grid,a,b);//对于下一个合理的位置进行递归
        }
        return res;
    }
}

水位上升的泳池中游泳

水位上升的泳池中游泳

将元素放入队列之前将元素进行标记 不会超时
将元素从队列中取出再将元素标记，会超时

class Solution {
    public int swimInWater(int[][] grid) {
        int n=grid.length;int m=grid[0].length;
        int left=grid[0][0];int right=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                right=Math.max(right,grid[i][j]);
            }
        }
        while(left<right){
            int mid=left+right>>1;
            if(check(grid,mid)){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};
    public boolean check(int[][] grid,int mid){
        Queue<int[]> queue=new LinkedList<int[]>();
        boolean[][] vis=new boolean[grid.length][grid[0].length];
        queue.offer(new int[]{0,0});
        vis[0][0]=true;
        while(!queue.isEmpty()){
            int[] node=queue.poll();
            int start=node[0];
            int end=node[1];
            // vis[start][end]=true;
            if(start==grid.length-1&&end==grid[0].length-1){
                return true;
            }
            for(int k=0;k<4;k++){
                int a=start+dx[k];
                int b=end+dy[k];
                if(a<0||a>=grid.length||b<0||b>=grid[0].length||vis[a][b]||grid[a][b]>mid){
                    continue;
                }
                vis[a][b]=true;
                queue.offer(new int[]{a,b});
            }
        }
        return false;
    }
}

最大人工岛

最大人工岛

class Solution {
    public int largestIsland(int[][] grid) {
        //将所有的陆地进行编号并计算大小
        int n=grid.length;int m=grid[0].length;
        int index=2;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        int res=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    int area=area(grid,i,j,index);
                    map.put(index,area);
                    res=Math.max(res,area);
                    index++;
                }
            }
        }

        if(res==Integer.MIN_VALUE){
            return 1;//所有的都是0海水
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    Set<Integer> set=getNeighbor(grid,i,j);//所有邻居陆地的index编号
                    int total=1;
                    for (Integer cur : set) {
                        total+=map.get(cur);
                    } 
                    res=Math.max(res,total);
                }
            }
        }
        return res;
    }

    public Set<Integer> getNeighbor(int[][] grid,int i,int j){
        Set<Integer> res=new HashSet<>();
        if(isArea(grid,i-1,j)&&grid[i-1][j]>1){
            res.add(grid[i-1][j]);
        }
        if (isArea(grid, i + 1, j) && grid[i + 1][j] > 1) {
            res.add(grid[i+1][j]);
        }
        if (isArea(grid, i, j - 1) && grid[i][j - 1] > 1) {
            res.add(grid[i][j-1]);
        }
        if (isArea(grid, i, j + 1) && grid[i][j + 1] > 1) {
            res.add(grid[i][j+1]);
        }
        return res;
    }

    public int area(int[][] grid,int i,int j,int index){
        if(!isArea(grid,i,j)){
            return 0;
        }
        //不是index编号
        if(grid[i][j]!=1){
            return 0;
        }
        grid[i][j]=index;
        return 1+area(grid,i-1,j,index)+area(grid,i+1,j,index)+area(grid,i,j-1,index)+area(grid,i,j+1,index);
    }

    public boolean isArea(int[][] grid,int i,int j){
        int n=grid.length;
        return i>=0&&i<n&&j>=0&&j<n;
    }
}