网格图 DFS

判断连通块个数、大小等。

部分题目也可以用 BFS 或并查集解决。

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution {
    int m,n;
    public int numIslands(char[][] grid) {
        int count=0;
        m=grid.length; 
        n=grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
​
    public void dfs(char[][] grid, int y, int x) {
        if (y >= m || x >= n || y < 0 || x < 0) {
            return;
        }
        if (grid[y][x] != '1') {
            return;
        }
        
        grid[y][x] = 'T';
        
​
        dfs(grid, y-1, x);
        dfs(grid, y+1, x);
        dfs(grid, y, x-1);
        dfs(grid, y, x+1);
    }
}

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution {
    int m,n;
    public int maxAreaOfIsland(int[][] grid) {
        int area=0;
        m=grid.length; 
        n=grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    int cur=dfs(grid, i, j);
                    // System.out.println(i + " " + j +" "+cur);
                    area=Math.max(area,cur);
                }
            }
        }
        return area;
    }
​
    public int dfs(int[][] grid, int y, int x) {
        if (y>=m || x>=n || x<0 || y<0) {
            return 0;
        }
        if (grid[y][x] != 1) {
            return 0;
        }
        grid[y][x] = -1;
        return dfs(grid,y-1,x)+dfs(grid,y+1,x)+dfs(grid,y,x-1)+dfs(grid,y,x+1)+1;
    }
}

面试题 16.19. 水域大小

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

class Solution {
    int m,n;
    public int[] pondSizes(int[][] land) {
        List<Integer> areas = new ArrayList<>();
        m=land.length;
        n=land[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (land[i][j] == 0) {
                    int area=dfs(land, i, j);
                    areas.add(area);
                }
            }
        }
        int[] ans=new int[areas.size()];
        for (int i=0; i<areas.size(); i++) {
            ans[i]=areas.get(i);
        }
        Arrays.sort(ans);
        return ans;
    }
​
    public int dfs(int[][] land, int y, int x) {
        if (y>=m || x>=n || y<0 || x<0) {
            return 0;
        }
        if (land[y][x] != 0) {
            return 0;
        }
        land[y][x] = -1;
        return 1+dfs(land,y-1,x)+dfs(land,y+1,x)+dfs(land,y,x+1)+dfs(land,y,x-1)+dfs(land,y-1,x-1)+dfs(land,y-1,x+1)+dfs(land,y+1,x-1)+dfs(land,y+1,x+1);
    }
}

LCS 03. 主题空间

「以扣会友」线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 grid，字符串中仅包含 "0"～"5" 这 6 个字符。地图上每一个字符代表面积为 1 的区域，其中 "0" 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。

假如整个 grid 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 0。

class Solution {
    int m,n;
​
    public int largestArea(String[] grid) {
        m=grid.length;
        n=grid[0].length();
        int[][] space=new int[m][n];
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                space[i][j] = grid[i].charAt(j) -'0';
            }
        }
​
        // for (int i=0; i<m; i++) {
        //     for (int j=0; j<n; j++) {
        //         System.out.print(space[i][j] + " ");
        //     }
        //     System.out.println();
        // }
​
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (space[i][j] > 0 && isValid(space, i, j)) {
                    dfs(space, i, j, space[i][j]);
                }
            }
        }
        // System.out.println();
        // for (int i=0; i<m; i++) {
        //     for (int j=0; j<n; j++) {
        //         System.out.print(space[i][j] + " ");
        //     }
        //     System.out.println();
        // }
​
        int ans=0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (space[i][j] > 0) {
                    int area = areaDfs(space, i, j, space[i][j]);
                    ans=Math.max(ans, area);
                }
            }
        }
        return ans;
    }
​
    public boolean isValid(int[][] space, int y, int x) {
        if (y==m-1 || x==n-1 || x==0 || y==0) {
            return true;
        }
        if (y-1>=0 && space[y-1][x] == 0) {
            return true;
        }
        if (y+1<m && space[y+1][x] == 0) {
            return true;
        }
        if (x-1>=0 && space[y][x-1] == 0) {
            return true;
        }
        if (x+1<n && space[y][x+1] == 0) {
            return true;
        }
        return false;
    }
​
    public void dfs(int[][] space, int y, int x, int value) {
        if (y>=m || x>=n || x<0 || y<0) {
            return;
        }
        if (space[y][x] != value) {
            return;
        }
        space[y][x]=-1;
        dfs(space, y-1, x, value);
        dfs(space, y+1, x, value);
        dfs(space, y, x-1, value);
        dfs(space, y, x+1, value);
    }
​
    public int areaDfs(int[][] space, int y, int x, int value) {
        if (y>=m || x>=n || x<0 || y<0) {
            return 0;
        }
        if (space[y][x] != value) {
            return 0;
        }
        space[y][x]=-2;
        int up=areaDfs(space, y-1, x, value);
        int down=areaDfs(space, y+1, x, value);
        int left=areaDfs(space, y, x-1, value);
        int right=areaDfs(space, y, x+1, value);
        return up+down+left+right+1;
    }
}

463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

class Solution {
    int m,n;
​
    public int islandPerimeter(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    int p=dfs(grid, i, j);
                    return p;
                }
            }
        }    
        return 0;
    }
​
    public int dfs(int[][] grid, int y, int x) {
        if (y>=m || y<0 || x>=n || x<0) {
            return 1;
        }
​
        if (grid[y][x] == 0) {
            return 1;
        }
​
        if (grid[y][x] == -1) {
            return 0;
        }
​
        grid[y][x] = -1;
​
        return dfs(grid, y-1,x) + dfs(grid,y+1,x)+dfs(grid,y,x-1)+dfs(grid,y,x+1);
    }
}

2658. 网格图中鱼的最大数目

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：

• 如果 grid[r][c] = 0 ，那么它是一块 陆地 。

• 如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。

一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：

• 捕捞格子 (r, c) 处所有的鱼，或者

• 移动到相邻的 水域 格子。

请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。

格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相邻格子在网格图内。

class Solution {
    int m,n;
    public int findMaxFish(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        int ans=0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] > 0) {
                    int fish=dfs(grid, i, j);
                    ans=Math.max(ans, fish);
                }
            }
        }
        return ans;
    }
​
    public int dfs(int[][] grid, int y, int x) {
        if (y<0 || x<0 || y>=m || x>=n) {
            return 0;
        }
        if (grid[y][x] <= 0) {
            return 0;
        }
        int fish=grid[y][x];
        grid[y][x]=-1;
        return fish+dfs(grid,y-1,x)+dfs(grid,y+1,x)+dfs(grid,y,x-1)+dfs(grid,y,x+1);
    }
}

1034. 边界着色

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。

如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：

• 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻

• 在网格的边界上（第一行/列或最后一行/列）

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色。

并返回最终的网格 grid 。

class Solution {
    int m,n;
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        m=grid.length;
        n=grid[0].length;
        int original=grid[row][col];
        dfs(grid, row, col, original);
        // for (int i=0; i<m; i++) {
        //     for (int j=0; j<n; j++) {
        //         System.out.print(grid[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = color;
                } else if (grid[i][j] == -1) {
                    grid[i][j] = original;
                }
            }
        }
        return grid;
    }
​
    public void dfs(int[][] grid, int row, int col, int color) {
        // System.out.println(row + " " + col + " " + color);
        if (row>=m || row<0 || col>=n || col<0) {
            return;
        }
        if (grid[row][col] != color) {
            return;
        }
        if (row==0 || row==m-1 || col==0 || col==n-1) {
            grid[row][col]=0;
        } 
        if (row+1<m && grid[row+1][col] != color && grid[row+1][col]>0) {
            grid[row][col] = 0;
        } 
        if (row-1>=0 && grid[row-1][col] != color && grid[row-1][col]>0) {
            grid[row][col] = 0;
        } 
        if (col+1<n && grid[row][col+1] != color && grid[row][col+1]>0) {
            grid[row][col] = 0;
        } 
        if (col-1>=0 && grid[row][col-1] != color && grid[row][col-1]>0) {
            grid[row][col] = 0;
        }
        if (grid[row][col] != 0) {
            grid[row][col] = -1;
        }
​
        dfs(grid, row-1, col, color);
        dfs(grid, row+1, col, color);
        dfs(grid, row, col-1, color);
        dfs(grid, row, col+1, color);
    }
}

1020. 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

class Solution {
    int m,n;
    public int numEnclaves(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j]>0&&isValid(i, j)) {
                    dfs(grid, i, j, grid[i][j]);
                }
            }
        }
        int ans=0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] > 0) {
                    ans += 1;
                }
            }
        }
        return ans;
​
    }
​
    public boolean isValid(int y, int x) {
        if (y==0 || x==0 || y==m-1 || x==n-1) {
            return true;
        }
        return false;
    }
​
    public void dfs(int[][] grid, int y, int x, int value) {
        if (y<0 || y>=m || x<0 || x>=n) {
            return;
        }
​
        if (grid[y][x] != value) {
            return;
        }
        grid[y][x]=-1;
        dfs(grid, y-1, x, value);
        dfs(grid, y+1, x, value);
        dfs(grid, y, x-1, value);
        dfs(grid, y, x+1, value);
    }
}

2684. 矩阵中移动的最大次数

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

• 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

class Solution {
    int m, n;
    int[][] memo;
​
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        memo = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            int step = dfs(grid, i, 0);
            ans = Math.max(ans, step);
        }
        return ans;
    }
​
    public int dfs(int[][] grid, int y, int x) {
        if (y < 0 || y >= m || x < 0 || x >= n) {
            return 0;
        }
        if (x == n - 1) return 0;
        if (memo[y][x] != 0) {
            return memo[y][x];
        }
​
        int cur = grid[y][x];
        int up = 0, mid = 0, down = 0;
        if (y - 1 >= 0 && grid[y - 1][x + 1] > cur) {
            up = dfs(grid, y - 1, x + 1) + 1;
        }
        if (grid[y][x + 1] > cur) {
            mid = dfs(grid, y, x + 1) + 1;
        }
        if (y + 1 < m && grid[y + 1][x + 1] > cur) {
            down = dfs(grid, y + 1, x + 1) + 1;
        }
​
        memo[y][x] = Math.max(up, Math.max(mid, down));
        return memo[y][x];
    }
}
​

1254. 统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

class Solution {
    int m,n;
    public int closedIsland(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        for (int i=0; i<m; i++) {
            if (grid[i][0] == 0) {
                kill(grid, i, 0);
            }
            if (grid[i][n-1] == 0) {
                kill(grid, i, n-1);
            }
        }
​
        for (int i=0; i<n; i++) {
            if (grid[0][i] == 0) {
                kill(grid, 0, i);
            }
            if (grid[m-1][i] == 0) {
                kill(grid, m-1, i);
            }
        }
        int ans=0;
        for (int i=1; i<m-1; i++) {
            for (int j=1; j<n-1; j++) {
                if (grid[i][j] == 0) {
                    ans++;
                    kill(grid, i, j);
                }
            }
        }
        return ans;
    }
​
    public void kill(int[][] grid, int y, int x) {
        if (y<0 || y>=m || x<0 || x>=n) {
            return;
        }
        if (grid[y][x] != 0) return;
        // -1代表不是封闭的
        grid[y][x]=-1;
        kill(grid, y-1, x);
        kill(grid, y+1, x);
        kill(grid, y, x-1);
        kill(grid, y, x+1);
    }
}

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：

• 连接：一个单元格与水平或垂直方向上相邻的单元格连接。

• 区域：连接所有 'O' 的单元格来形成一个区域。

• 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。

通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。

class Solution {
    int m,n;
    public void solve(char[][] board) {
        m=board.length;
        n=board[0].length;
        for (int i=0; i<m; i++) {
            if (board[i][0] == 'O') {
                find(board, i, 0, 'T');
            }
            if (board[i][n-1] == 'O') {
                find(board, i, n-1, 'T');
            }
        }
        for (int i=0; i<n; i++) {
            if (board[0][i] == 'O') {
                find(board, 0, i, 'T');
            }
            if (board[m-1][i] == 'O') {
                find(board, m-1, i, 'T');
            }
        }
​
        for (int i=1; i<m-1; i++) {
            for (int j=1; j<n-1; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
​
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (board[i][j] == 'T') {
                    board[i][j] ='O';
                }
            }
        }
​
​
    }
​
    public void find(char[][] board, int y, int x, char target) {
        if (y<0 || y>=m || x<0 || x>=n) return;
        if (board[y][x] != 'O') return;
​
        board[y][x] = target;
​
        find(board, y-1, x, target);
        find(board, y+1, x, target);
        find(board, y, x-1, target);
        find(board, y, x+1, target);
    }
}

1905. 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

class Solution {
    int m,n;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        m=grid1.length;
        n=grid1[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid1[i][j] == 1 && grid2[i][j] == 1) {
                    grid2[i][j]=2;
                }
            }
        }
        int ans=0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid2[i][j] == 2 && onlyTwo(grid2, i, j)) {
                    ans+=1;
                }
            }
        }
        return ans;
    }

    public boolean onlyTwo(int[][] grid, int y, int x) {
        if (y>=m || y<0 || x>=n || x<0) {
            return true;
        }
        //如果是海洋，ok的
        if (grid[y][x] != 2) return grid[y][x] == 0;
        // boolean only2=true;
        grid[y][x] = 0;
        boolean down = onlyTwo(grid, y-1, x);
        boolean up = onlyTwo(grid, y+1, x);
        boolean left = onlyTwo(grid, y, x-1);
        boolean right= onlyTwo(grid, y, x+1);
        return down & up & left & right;
    }
}

1391. 检查网格中是否存在有效路径

class Solution {
    int m,n;
    boolean[][] vis;
    int[][][] directions = new int[][][]{{}, {{0,1},{0,-1}}, {{1,0},{-1,0}}, {{1,0}, {0,-1}}, {{0,1}, {1,0}}, {{-1,0},{0,-1}}, {{0,1},{-1,0}}};
    int last=0;
    public boolean hasValidPath(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        vis = new boolean[m][n];
        return dfs(grid,0 ,0);
    }
​
    public boolean dfs(int[][] grid, int y, int x) {
        
        if (y==m-1 && x==n-1) return true;
        vis[y][x] = true;
        int type=grid[y][x];
        int[][] direction = directions[type];
        
        for (int[] dir : direction) {
            int newX = x+dir[1];
            int newY = y+dir[0];
            if (newX>=0 && newY>=0 && newX<n && newY<m && !vis[newY][newX] 
                && check(grid, y, x, newY, newX)) {
                if (dfs(grid, newY, newX)) {
                    return true;
                }
            }
        }
        
        return false;
    }
​
    boolean check(int[][] grid, int y, int x, int newY, int newX) {
        for (int[] d : directions[grid[newY][newX]])
            if (newX + d[1] == x && newY + d[0] == y)
                return true;
        return false;
    }
}

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

class Solution {
    int m, n;
    boolean[][] pacificReachable, atlanticReachable;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向：下、上、右、左
​
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        pacificReachable = new boolean[m][n];
        atlanticReachable = new boolean[m][n];
​
        // 从边界开始 DFS
        for (int i = 0; i < m; i++) {
            dfs(heights, i, 0, pacificReachable); // 左边界（太平洋）
            dfs(heights, i, n - 1, atlanticReachable); // 右边界（大西洋）
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, 0, j, pacificReachable); // 上边界（太平洋）
            dfs(heights, m - 1, j, atlanticReachable); // 下边界（大西洋）
        }
​
        // 收集能同时流向太平洋和大西洋的点
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    List<Integer> coordinate = new ArrayList<>();
                    coordinate.add(i);
                    coordinate.add(j);
                    result.add(coordinate);
                }
            }
        }
        return result;
    }
​
    private void dfs(int[][] heights, int y, int x, boolean[][] reachable) {
        reachable[y][x] = true;
        for (int[] direction : directions) {
            int newY = y + direction[0];
            int newX = x + direction[1];
            // 检查新位置是否在矩阵范围内，且是否可以向上流动
            if (newY >= 0 && newY < m && newX >= 0 && newX < n &&
                !reachable[newY][newX] && heights[newY][newX] >= heights[y][x]) {
                dfs(heights, newY, newX, reachable);
            }
        }
    }
}
​

网格图 BFS

队列！

1926. 迷宫中离入口最近的出口

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

class Solution {
    int m,n;
    boolean[][] vis;
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    public int nearestExit(char[][] maze, int[] entrance) {
        m=maze.length;
        n=maze[0].length;
        vis=new boolean[m][n];
        vis[entrance[0]][entrance[1]] = true;
        Queue<int[]> queue=new LinkedList<>();

        queue.offer(new int[]{entrance[0], entrance[1], 0});

        while (!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1], step=cur[2];
            
            if ((y==m-1 || y==0 || x==n-1 || x==0 ) && !(y==entrance[0] && x==entrance[1])) {
                return step;
            }

            for (int[] dir : dirs) {
                int newY=y+dir[0], newX=x+dir[1];
                if (newY<m && newX<n && newY>=0 && newX>=0 && maze[newY][newX] == '.' && !vis[newY][newX]) {
                    vis[newY][newX] = true;
                    queue.offer(new int[]{newY, newX, step+1});
                }
            }

        }
        return -1;
    }
}

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格的值都是 0 。

• 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

class Solution {
    int m,n;
    boolean[][] vis;
    int[][] dirs=new int[][]{{1,1}, {1,-1}, {-1,1}, {-1,-1}, {0,1}, {1,0}, {0,-1}, {-1,0}};
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] != 0) return -1;

        m=grid.length;
        n=grid[0].length;
        vis = new boolean[m][n];
        Queue<int[]> queue=new LinkedList<>();
        queue.add(new int[]{0, 0, 1});
        vis[0][0] = true;
        while (!queue.isEmpty()) {
            int[] current=queue.poll();

            int y=current[0], x=current[1], step=current[2];

            if (y==m-1 && x==n-1) return step;

            for(int[] dir : dirs){
                int newY=y+dir[0];
                int newX=x+dir[1];
                if (newY>=0 && newY<m && newX>=0 && newX<n && !vis[newY][newX] && grid[newY][newX] == 0) {
                    vis[newY][newX] = true;
                    queue.offer(new int[]{newY, newX, step+1});
                }
            }
        }
        return -1;

    }
}

1162. 地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

class Solution {
    int[][] dirs=new int[][]{{0,-1},{-1,0},{0,1},{1,0}};
    public int maxDistance(int[][] grid) {
        int max=-1;
        int n=grid.length;
        
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        if (queue.isEmpty() || queue.size() == n*n) return -1;

        boolean[][] vis=new boolean[n][n];
        while (!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1];
            // vis[y][x] = true;
            for (int[] dir : dirs) {
                int newY = y+dir[0];
                int newX = x+dir[1];
                if (newY>=0 && newY<n && newX>=0 && newX<n && !vis[newY][newX] && grid[newY][newX] == 0) {
                    queue.offer(new int[]{newY, newX});
                    vis[newY][newX] = true;
                    grid[newY][newX] = grid[y][x] + 1;
                    max=Math.max(max, grid[newY][newX]-1);
                }
            }
        }
        return max;
    }
}

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

class Solution {
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};

    public int[][] updateMatrix(int[][] mat) {
        int m=mat.length, n=mat[0].length;

        boolean[][] vis=new boolean[m][n];

        Queue<int[]> queue=new LinkedList<>();

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    vis[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1];

            for (int[] dir : dirs) {
                int newY=y+dir[0], newX=x+dir[1];

                if (newY>=0 && newY<m && newX>=0 && newX<n && !vis[newY][newX] && mat[newY][newX]!=0) {
                    vis[newY][newX] = true;
                    mat[newY][newX] += mat[y][x];
                    queue.offer(new int[]{newY, newX});
                }
            }
        }
        return mat;

    }
}

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；

• 值 1 代表新鲜橘子；

• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

class Solution {
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    public int orangesRotting(int[][] grid) {
        int m=grid.length, n=grid[0].length;
        int ans=0;
        boolean[][] vis=new boolean[m][n];
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0});
                }
            }
        }

        while(!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1], step=cur[2];
            grid[y][x] = 2;
            ans=Math.max(ans, step);
            for (int[] dir : dirs) {
                int newY=y+dir[0], newX=x+dir[1];
                if (newY<m && newY>=0 && newX<n && newX>=0 && !vis[newY][newX] && grid[newY][newX] == 1) {
                    vis[newY][newX] = true;
                    
                    queue.offer(new int[]{newY, newX, step+1});
                }
            }
            
        }
        for (int i=0;i<m; i++) {
            for (int j=0;j<n; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}

1765. 地图中的最高点

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

• 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。

• 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度：

• 每个格子的高度都必须是非负的。

• 如果一个格子是 水域 ，那么它的高度必须为 0 。

• 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

class Solution {
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    public int[][] highestPeak(int[][] isWater) {
        int m=isWater.length;
        int n=isWater[0].length;
        boolean[][] vis=new boolean[m][n];
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (isWater[i][j] == 1) {
                    vis[i][j] = true;
                    isWater[i][j] = 0;
                    queue.offer(new int[] {i, j, 0});
                }
            }
        }
​
        while (!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1], height=cur[2];
​
            for (int[] dir:dirs) {
                int newY=y+dir[0], newX=x+dir[1];
                if (newY<m && newX<n && newY>=0 && newX>=0 && !vis[newY][newX]) {
                    int newH = height+1;
                    isWater[newY][newX] = newH;
                    vis[newY][newX] = true;
                    queue.offer(new int[] {newY, newX, newH});
                }
            }
​
        }
        return isWater;
    }
}

934. 最短的桥

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 0 的最小数目。

class Solution {
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    int n;
    public int shortestBridge(int[][] grid) {
        n=grid.length;
        boolean[][] vis=new boolean[n][n];
        Queue<int[]> queue=new LinkedList<>();
​
        boolean found=false;
        for (int i=0;i<n && !found; i++) {
            for (int j=0; j<n && !found; j++) {
                if (grid[i][j] == 1) {
                    found=true;
                    trans(grid, i, j, queue, vis);
                }
            }
        }
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
        while (!queue.isEmpty()) {
            int size=queue.size();
            int step=1;
            for (int k=0; k<size; k++) {
                int[] cur=queue.poll();
                int i=cur[0], j=cur[1];
                
                for (int[] dir:dirs) {
                    int newY=dir[0]+i, newX=dir[1]+j;
                    if (newY<n && newY>=0 && newX<n && newX>=0 && !vis[newY][newX]) {
                        if (grid[newY][newX] == 1) {
                            return step;
                        } 
                        if (grid[newY][newX] == 0) {
                            vis[newY][newX] = true;
                            queue.offer(new int[] {newY, newX});
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
​
    public void trans(int[][] grid, int y, int x, Queue<int[]> queue, boolean[][] vis) {
        vis[y][x]=true;
        grid[y][x] = 2;
        queue.offer(new int[]{y, x});
        Queue<int[]> isLand=new LinkedList<>();
        isLand.offer(new int[]{y, x});
        while (!isLand.isEmpty()) {
            int[] cur=isLand.poll();
            int i=cur[0], j=cur[1];
            
            for (int[] dir:dirs) {
                int newY=dir[0]+i, newX=dir[1]+j;
                if (newY<n && newY>=0 && newX<n && newX>=0 && !vis[newY][newX] && grid[newY][newX] == 1) {
                    grid[newY][newX] = 2;
                    vis[newY][newX] = true;
                    isLand.offer(new int[]{newY, newX});
                    queue.offer(new int[] {newY, newX});
                }
            }
        }
    }
}

1293. 网格中的最短路径

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

class Solution {
    int[][] dirs=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    public int shortestPath(int[][] grid, int k) {
        int m=grid.length, n=grid[0].length;
        if (m==1 && n==1) return 0;
        boolean[][][] vis=new boolean[m][n][k+1];
        Queue<int[]> queue=new LinkedList<>();
        vis[0][0][k]=true;
        queue.offer(new int[]{0, 0, k, 0});
​
        while (!queue.isEmpty()) {
            int[] cur=queue.poll();
            int y=cur[0], x=cur[1], remain=cur[2], step=cur[3];
            if (y==m-1 && x==n-1) {
                return step;
            }
            for (int[] dir : dirs) {
                int newY=y+dir[0], newX=x+dir[1];
​
                if (newY>=0 && newY<m && newX>=0 && newX<n ) {
                    
                    if (grid[newY][newX] == 0 && !vis[newY][newX][remain]) {
                        vis[newY][newX][remain] = true;
                        queue.offer(new int[] {newY, newX, remain, step+1});
                    }
​
                    if (grid[newY][newX] == 1 && remain > 0 && !vis[newY][newX][remain-1]) {
                        vis[newY][newX][remain-1] = true;
                        queue.offer(new int[] {newY, newX, remain-1, step+1});
                    }
​
                    
                }
            }
        }
        return -1;
    }
}
//0,0,0,0,0,0,0,0,0,0
//0,1,1,1,1,1,1,1,1,0
//0,1,0,0,0,0,0,0,0,0
//0,1,0,1,1,1,1,1,1,1
//0,1,0,0,0,0,0,0,0,0
//0,1,1,1,1,1,1,1,1,0
//0,1,0,0,0,0,0,0,0,0
//0,1,0,1,1,1,1,1,1,1
//0,1,0,1,1,1,1,0,0,0
//0,1,0,0,0,0,0,0,1,0
//0,1,1,1,1,1,1,0,1,0
//0,0,0,0,0,0,0,0,1,0