• LeetCode —— dfs和bfs

    797. 所有可能的路径

    给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

    示例1：输入：graph = [[1,2],[3],[3],[]]         输出：[[0,1,3],[0,2,3]] 

    示例2：输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]      输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

    1. // dfs
    2. class Solution {
    3.     List> list = new ArrayList<>();
    4.     LinkedList path = new LinkedList<>();
    5.  
    6.     public List> allPathsSourceTarget(int[][] graph) {
    7.         path.add(0);
    8.         dfs(graph, 0);
    9.         return list;
    10.     }
    11.  
    12.     public void dfs(int[][] graph, int node){
    13.         if(node == graph.length - 1){
    14.             list.add(new ArrayList<>(path));
    15.             return;
    16.         }
    17.  
    18.         for(int i = 0; i < graph[node].length; i++){
    19.             path.add(graph[node][i]);
    20.             dfs(graph, graph[node][i]);
    21.             path.removeLast();
    22.         }
    23.     }
    24. }

    200. 岛屿数量

    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

    示例1：

    输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

    1. // dfs （以下三种方式等价）
    2. class Solution {
    3.     public int numIslands(char[][] grid) {
    4.         int count = 0;
    5.         for(int i = 0; i < grid.length; i++){
    6.             for(int j = 0; j < grid[0].length; j++){
    7.                 if(grid[i][j] == '1'){
    8.                     count++;
    9.                     dfs(grid, i, j);
    10.                 }
    11.             }
    12.         }
    13.         return count;
    14.     }
    15.  
    16.     public void dfs(char[][] grid, int i, int j){
    17.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
    18.             return;
    19.         }
    20.         grid[i][j] = '0';
    21.         dfs(grid, i - 1, j);
    22.         dfs(grid, i + 1, j);
    23.         dfs(grid, i, j - 1);
    24.         dfs(grid, i, j + 1);
    25.     }
    26. }
    27.  
    28.  
    29. class Solution {
    30.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    31.     public int numIslands(char[][] grid) {
    32.         int count = 0;
    33.         for(int i = 0; i < grid.length; i++){
    34.             for(int j = 0; j < grid[0].length; j++){
    35.                 if(grid[i][j] == '1'){
    36.                     count++;
    37.                     dfs(grid, i, j);
    38.                 }
    39.             }
    40.         }
    41.         return count;
    42.     }
    43.  
    44.     public void dfs(char[][] grid, int i, int j){
    45.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
    46.             return;
    47.         }
    48.  
    49.         grid[i][j] = '0';
    50.         for(int[] pos : positions){
    51.             int newRow = i + pos[0];
    52.             int newColumn = j + pos[1];
    53.             dfs(grid, newRow, newColumn);
    54.         }
    55.     }
    56. }
    57.  
    58.  
    59. class Solution {
    60.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    61.     boolean[][] visited;        // 通过判断该位置是否被访问过，而不是将1修改为0
    62.  
    63.     public int numIslands(char[][] grid) {
    64.         visited = new boolean[grid.length][grid[0].length];
    65.         int count = 0;
    66.         for(int i = 0; i < grid.length; i++){
    67.             for(int j = 0; j < grid[0].length; j++){
    68.                 if(grid[i][j] == '1' && !visited[i][j]){
    69.                     count++;
    70.                     dfs(grid, i, j);
    71.                 }
    72.             }
    73.         }
    74.         return count;
    75.     }
    76.  
    77.     public void dfs(char[][] grid, int i, int j){
    78.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || visited[i][j] || grid[i][j] == '0'){
    79.             return;
    80.         }
    81.  
    82.         visited[i][j] = true;
    83.         for(int[] pos : positions){
    84.             int newRow = i + pos[0];
    85.             int newColumn = j + pos[1];
    86.             dfs(grid, newRow, newColumn);
    87.         }
    88.     }
    89. }
    1. // bfs      以下三种方式等价
    2. class Solution {
    3.     public int numIslands(char[][] grid) {
    4.         int count = 0;
    5.         for(int i = 0; i < grid.length; i++){
    6.             for(int j = 0; j < grid[0].length; j++){
    7.                 if(grid[i][j] == '1'){
    8.                     count++;
    9.                     bfs(grid, i, j);
    10.                 }
    11.             }
    12.         }
    13.         return count;
    14.     }
    15.  
    16.     public void bfs(char[][] grid, int i, int j){
    17.         Queue<int[]> queue = new LinkedList<>();
    18.         queue.offer(new int[]{i, j});
    19.         while(!queue.isEmpty()){
    20.             int[] cur = queue.poll();
    21.             i = cur[0];
    22.             j = cur[1];
    23.             if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
    24.                 continue;
    25.             }
    26.             grid[i][j] = '0';
    27.             queue.offer(new int[]{i - 1, j});
    28.             queue.offer(new int[]{i + 1, j});
    29.             queue.offer(new int[]{i, j - 1});
    30.             queue.offer(new int[]{i, j + 1});
    31.         }
    32.     }
    33. }
    34.  
    35.  
    36. class Solution {
    37.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    38.     public int numIslands(char[][] grid) {
    39.         int count = 0;
    40.         for(int i = 0; i < grid.length; i++){
    41.             for(int j = 0; j < grid[0].length; j++){
    42.                 if(grid[i][j] == '1'){
    43.                     count++;
    44.                     bfs(grid, i, j);
    45.                 }
    46.             }
    47.         }
    48.         return count;
    49.     }
    50.  
    51.     public void bfs(char[][] grid, int i, int j){
    52.         Queue<int[]> queue = new LinkedList();
    53.         queue.offer(new int[]{i, j});
    54.         grid[i][j] = '0';
    55.         while(!queue.isEmpty()){
    56.             int[] cur = queue.poll();
    57.             for(int[] pos : positions){
    58.                 int newRow = cur[0] + pos[0];
    59.                 int newColumn = cur[1] + pos[1];
    60.                 if(newRow < 0 || newRow >= grid.length || newColumn < 0 || newColumn >= grid[0].length || grid[newRow][newColumn] == '0'){
    61.                     continue;
    62.                 }
    63.                 grid[newRow][newColumn] = '0';   // 防止下次for循环将同样的位置（下次计算得到的newRow,newColumn可能会与本次相同）加入queue中，造成死循环
    64.                 queue.offer(new int[]{newRow, newColumn});
    65.             }
    66.         }
    67.     }
    68. }
    69.  
    70.  
    71. class Solution {
    72.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    73.     boolean[][] visited;        // 通过判断该位置是否被访问过，而不是将1修改为0
    74.  
    75.     public int numIslands(char[][] grid) {
    76.         visited = new boolean[grid.length][grid[0].length];
    77.         int count = 0;
    78.         for(int i = 0; i < grid.length; i++){
    79.             for(int j = 0; j < grid[0].length; j++){
    80.                 if(grid[i][j] == '1' && !visited[i][j]){
    81.                     count++;
    82.                     bfs(grid, i, j);
    83.                 }
    84.             }
    85.         }
    86.         return count;
    87.     }
    88.  
    89.     public void bfs(char[][] grid, int i, int j){
    90.         Queue<int[]> queue = new LinkedList();
    91.         queue.offer(new int[]{i, j});
    92.         visited[i][j] = true;
    93.         while(!queue.isEmpty()){
    94.             int[] cur = queue.poll();
    95.             for(int[] pos : positions){
    96.                 int newRow = cur[0] + pos[0];
    97.                 int newColumn = cur[1] + pos[1];
    98.                 if(newRow < 0 || newRow >= grid.length || newColumn < 0 || newColumn >= grid[0].length || grid[newRow][newColumn] == '0' || visited[newRow][newColumn]){
    99.                     continue;
    100.                 }
    101.                 visited[newRow][newColumn] = true;
    102.                 queue.offer(new int[]{newRow, newColumn});
    103.             }
    104.         }
    105.     }
    106. }

    695. 岛屿的最大面积

    给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

    输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
    1. // dfs
    2. class Solution {
    3.     int area;
    4.     public int maxAreaOfIsland(int[][] grid) {
    5.         int maxArea = 0;
    6.         for(int i = 0; i < grid.length; i++){
    7.             for(int j = 0; j < grid[0].length; j++){
    8.                 if(grid[i][j] == 1){
    9.                     area = 0;
    10.                     dfs(grid, i, j);
    11.                     maxArea = Math.max(maxArea, area);
    12.                 }
    13.             }
    14.         }
    15.         return maxArea;
    16.     }
    17.  
    18.     public void dfs(int[][] grid, int i, int j){
    19.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
    20.             return;
    21.         }
    22.         area++;
    23.         grid[i][j] = 0;
    24.         dfs(grid, i - 1, j);
    25.         dfs(grid, i + 1, j);
    26.         dfs(grid, i, j - 1);
    27.         dfs(grid, i, j + 1);
    28.     }
    29. }
    1. // bfs
    2. class Solution {
    3.     int area;
    4.     public int maxAreaOfIsland(int[][] grid) {
    5.         int maxArea = 0;
    6.         for(int i = 0; i < grid.length; i++){
    7.             for(int j = 0; j < grid[0].length; j++){
    8.                 if(grid[i][j] == 1){
    9.                     area = 0;
    10.                     bfs(grid, i, j);
    11.                     maxArea = Math.max(maxArea, area);
    12.                 }
    13.             }
    14.         }
    15.         return maxArea;
    16.     }
    17.  
    18.     public void bfs(int[][] grid, int i, int j){
    19.         Queue<int[]> queue = new LinkedList<>();
    20.         queue.offer(new int[]{i, j});
    21.         while(!queue.isEmpty()){
    22.             int[] cur = queue.poll();
    23.             i = cur[0];
    24.             j = cur[1];
    25.             if(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
    26.                 area++;
    27.                 grid[i][j] = 0;
    28.                 queue.offer(new int[]{i - 1, j});
    29.                 queue.offer(new int[]{i + 1, j});
    30.                 queue.offer(new int[]{i, j - 1});
    31.                 queue.offer(new int[]{i, j + 1});
    32.             }
    33.         }
    34.     }
    35. }

    463. 岛屿的周长

    给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

    示例：输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]         输出：16

    1. // dfs
    2. class Solution {
    3.     int count = 0;
    4.     public int islandPerimeter(int[][] grid) {
    5.         for(int i = 0; i < grid.length; i++){
    6.             for(int j = 0; j < grid[0].length; j++){
    7.                 if(grid[i][j] == 1){
    8.                     dfs(grid, i, j);
    9.                 }
    10.             }
    11.         }
    12.         return count;
    13.     }
    14.  
    15.     public void dfs(int[][] grid, int i, int j){
    16.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
    17.             count++;
    18.             return;
    19.         }
    20.         if(grid[i][j] == 2){
    21.             return;
    22.         }
    23.         grid[i][j] = 2;
    24.         dfs(grid, i - 1, j);
    25.         dfs(grid, i + 1, j);
    26.         dfs(grid, i, j - 1);
    27.         dfs(grid, i, j + 1);
    28.     }
    29. }
    30.  
    31.  
    32. class Solution {
    33.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    34.     boolean[][] visited;
    35.     int count;
    36.     public int islandPerimeter(int[][] grid) {
    37.         visited = new boolean[grid.length][grid[0].length];
    38.         for(int i = 0; i < grid.length; i++){
    39.             for(int j = 0; j < grid[0].length; j++){
    40.                 if(grid[i][j] == 1 && !visited[i][j]){
    41.                     dfs(grid, i, j);
    42.                 }
    43.             }
    44.         }
    45.         return count;
    46.     }
    47.  
    48.     public void dfs(int[][] grid, int i, int j){
    49.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
    50.             count++;
    51.             return;
    52.         }
    53.         if(visited[i][j] && grid[i][j] == 1){
    54.             return;
    55.         }
    56.  
    57.         visited[i][j] = true;
    58.         for(int[] pos : positions){
    59.             int newRow = i + pos[0];
    60.             int newColumn = j + pos[1];
    61.             dfs(grid, newRow, newColumn);
    62.         }
    63.     }
    64. }
    1. // bfs
    2. class Solution {
    3.     int count = 0;
    4.     public int islandPerimeter(int[][] grid) {
    5.         for(int i = 0; i < grid.length; i++){
    6.             for(int j = 0; j < grid[0].length; j++){
    7.                 if(grid[i][j] == 1){
    8.                     bfs(grid, i, j);
    9.                 }
    10.             }
    11.         }
    12.         return count;
    13.     }
    14.  
    15.     public void bfs(int[][] grid, int i, int j){
    16.         Queue<int[]> queue = new LinkedList<>();
    17.         queue.offer(new int[]{i, j});
    18.         while(!queue.isEmpty()){
    19.             int[] cur = queue.poll();
    20.             i = cur[0];
    21.             j = cur[1];
    22.             if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
    23.                 count++;
    24.                 continue;
    25.             }
    26.             if(grid[i][j] == 2){
    27.                 continue;
    28.             }
    29.             
    30.             grid[i][j] = 2;
    31.             queue.offer(new int[]{i - 1, j});
    32.             queue.offer(new int[]{i + 1, j});
    33.             queue.offer(new int[]{i, j - 1});
    34.             queue.offer(new int[]{i, j + 1});
    35.         }
    36.     }
    37. }
    38.  
    39.  
    40. class Solution {
    41.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    42.     boolean[][] visited;
    43.     int count = 0;
    44.     public int islandPerimeter(int[][] grid) {
    45.         visited = new boolean[grid.length][grid[0].length];
    46.         for(int i = 0; i < grid.length; i++){
    47.             for(int j = 0; j < grid[0].length; j++){
    48.                 if(grid[i][j] == 1 && !visited[i][j]){
    49.                     bfs(grid, i, j);
    50.                 }
    51.             }
    52.         }
    53.         return count;
    54.     }
    55.  
    56.     public void bfs(int[][] grid, int i, int j){
    57.         Queue<int[]> queue = new LinkedList<>();
    58.         queue.offer(new int[]{i, j});
    59.         visited[i][j] = true;
    60.         while(!queue.isEmpty()){
    61.             int[] cur = queue.poll();
    62.             for(int[] pos : positions){
    63.                 int newRow = cur[0] + pos[0];
    64.                 int newColumn = cur[1] + pos[1];
    65.                 if(newRow < 0 || newRow >= grid.length || newColumn < 0 || newColumn >= grid[0].length || grid[newRow][newColumn] == 0){
    66.                     count++;
    67.                     continue;
    68.                 }
    69.                 if(visited[newRow][newColumn] && grid[newRow][newColumn] == 1){
    70.                     continue;
    71.                 }
    72.                 queue.offer(new int[]{newRow, newColumn});
    73.                 visited[newRow][newColumn] = true;
    74.             }
    75.         }
    76.     }
    77. }

    827. 最大人工岛屿

    给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿 由一组上、下、左、右四个方向相连的 1 形成。

    示例：输入: grid = [[1, 0], [0, 1]]         输出: 3

    1. // dfs
    2. class Solution {
    3.     int islandSize;        // 每个岛屿的大小
    4.  
    5.     public int largestIsland(int[][] grid) {
    6.         int[][] positions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    7.         int m = grid.length;
    8.         int n = grid[0].length;
    9.  
    10.         Map map = new HashMap<>();    // key为岛屿编号，value为岛屿大小
    11.         int islandNumber = 2;                           // 岛屿编号从2开始，与0和1进行区分
    12.         for(int i = 0; i < m; i++){
    13.             for(int j = 0; j < n; j++){
    14.                 if(grid[i][j] == 1){
    15.                     islandSize = 0;
    16.                     dfs(grid, i, j, islandNumber);
    17.                     map.put(islandNumber, islandSize);
    18.                     islandNumber++;
    19.                 }
    20.             }
    21.         }
    22.  
    23.         int result = Integer.MIN_VALUE;
    24.         for(int i = 0; i < m; i++){
    25.             for(int j = 0; j < n; j++){
    26.                 if(grid[i][j] != 0){
    27.                     continue;
    28.                 }
    29.                 int curSize = 1;
    30.                 Set set = new HashSet<>();
    31.                 for(int[] pos : positions){
    32.                     int newRow = i + pos[0];
    33.                     int newColumn = j + pos[1];
    34.                     if(newRow < 0 || newRow >= m || newColumn < 0 || newColumn >= n || grid[newRow][newColumn] == 0){
    35.                         continue;
    36.                     }
    37.                     islandNumber = grid[newRow][newColumn];
    38.                     if(set.contains(islandNumber) || !map.containsKey(islandNumber)){
    39.                         continue;
    40.                     }
    41.                     set.add(islandNumber);
    42.                     curSize += map.get(islandNumber);
    43.                 }
    44.                 result = Math.max(result, curSize);
    45.             }
    46.         }
    47.         return result == Integer.MIN_VALUE ? m * n : result;
    48.     }
    49.  
    50.     public void dfs(int[][] grid, int i, int j, int islandNumber){
    51.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1){
    52.             return;
    53.         }
    54.         islandSize++;
    55.         grid[i][j] = islandNumber;
    56.         dfs(grid, i - 1, j, islandNumber);
    57.         dfs(grid, i + 1, j, islandNumber);
    58.         dfs(grid, i, j - 1, islandNumber);
    59.         dfs(grid, i, j + 1, islandNumber);
    60.     }
    61. }

    1020. 飞地的数量

    给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

    示例：输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]         输出：3

    1. // dfs
    2. class Solution {
    3.     public int numEnclaves(int[][] grid) {
    4.         for(int i = 0; i < grid.length; i++){   
    5.             if(grid[i][0] == 1){      // 左侧
    6.                 dfs(grid, i, 0);
    7.             }
    8.             if(grid[i][grid[0].length - 1] == 1){     // 右侧
    9.                 dfs(grid, i, grid[0].length - 1);
    10.             }
    11.         }
    12.         for(int j = 1; j < grid[0].length - 1; j++){    
    13.             if(grid[0][j] == 1){      // 上侧
    14.                 dfs(grid, 0, j);
    15.             }
    16.             if(grid[grid.length - 1][j] == 1){      // 下侧
    17.                 dfs(grid, grid.length - 1, j);
    18.             }
    19.         }
    20.  
    21.         int count = 0;
    22.         for(int i = 0; i < grid.length; i++){
    23.             for(int j = 0; j < grid[0].length; j++){
    24.                 if(grid[i][j] == 1){
    25.                     count++;
    26.                 }
    27.             }
    28.         }
    29.         return count;
    30.     }
    31.  
    32.     public void dfs(int[][] grid, int i, int j){
    33.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
    34.             return;
    35.         }
    36.         grid[i][j] = 0;
    37.         dfs(grid, i - 1, j);
    38.         dfs(grid, i + 1, j);
    39.         dfs(grid, i, j - 1);
    40.         dfs(grid, i, j + 1);
    41.     }
    42. }
    1. // bfs
    2. class Solution {
    3.     public int numEnclaves(int[][] grid) {
    4.         for(int i = 0; i < grid.length; i++){
    5.             if(grid[i][0] == 1){      // 左侧
    6.                 bfs(grid, i, 0);
    7.             }
    8.             if(grid[i][grid[0].length - 1] == 1){     // 右侧
    9.                 bfs(grid, i, grid[0].length - 1);
    10.             }
    11.         }
    12.         for(int j = 1; j < grid[0].length - 1; j++){
    13.             if(grid[0][j] == 1){      // 上侧
    14.                 bfs(grid, 0, j);
    15.             }
    16.             if(grid[grid.length - 1][j] == 1){      // 下侧
    17.                 bfs(grid, grid.length - 1, j);
    18.             }
    19.         }
    20.  
    21.         int count = 0;
    22.         for(int i = 0; i < grid.length; i++){
    23.             for(int j = 0; j < grid[0].length; j++){
    24.                 if(grid[i][j] == 1){
    25.                     count++;
    26.                 }
    27.             }
    28.         }
    29.         return count;
    30.     }
    31.  
    32.     public void bfs(int[][] grid, int i, int j){
    33.         Queue<int[]> queue = new LinkedList<>();
    34.         queue.offer(new int[]{i, j});
    35.         while(!queue.isEmpty()){
    36.             int[] cur = queue.poll();
    37.             i = cur[0];
    38.             j = cur[1];
    39.             if(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
    40.                 grid[i][j] = 0;
    41.                 queue.offer(new int[]{i - 1, j});
    42.                 queue.offer(new int[]{i + 1, j});
    43.                 queue.offer(new int[]{i, j - 1});
    44.                 queue.offer(new int[]{i, j + 1});
    45.             }
    46.         }
    47.     }
    48. }

    130. 被围绕的区域

    给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

    1. // dfs
    2. class Solution {
    3.     public void solve(char[][] board) {
    4.         for(int i = 0; i < board.length; i++){
    5.             if(board[i][0] == 'O'){
    6.                 dfs(board, i, 0);
    7.             }
    8.             if(board[i][board[0].length - 1] == 'O'){
    9.                 dfs(board, i, board[0].length - 1);
    10.             }
    11.         }
    12.  
    13.         for(int j = 1; j < board[0].length - 1; j++){
    14.             if(board[0][j] == 'O'){
    15.                 dfs(board, 0, j);
    16.             }
    17.             if(board[board.length - 1][j] == 'O'){
    18.                 dfs(board, board.length - 1, j);
    19.             }
    20.         }
    21.  
    22.         for(int i = 0; i < board.length; i++){
    23.             for(int j = 0; j < board[0].length; j++){
    24.                 if(board[i][j] == 'A'){
    25.                     board[i][j] = 'O';
    26.                 }else if(board[i][j] == 'O'){
    27.                     board[i][j] = 'X';
    28.                 }
    29.             }
    30.         }
    31.     }
    32.  
    33.     public void dfs(char[][] board, int i, int j){
    34.         if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' 
    35.              || board[i][j] == 'A'){
    36.             return;
    37.         }
    38.         board[i][j] = 'A';
    39.         dfs(board, i - 1, j);
    40.         dfs(board, i + 1, j);
    41.         dfs(board, i, j - 1);
    42.         dfs(board, i, j + 1);
    43.     }
    44. }
    1. // bfs
    2. class Solution {
    3.     public void solve(char[][] board) {
    4.         for(int i = 0; i < board.length; i++){
    5.             if(board[i][0] == 'O'){
    6.                 bfs(board, i, 0);
    7.             }
    8.             if(board[i][board[0].length - 1] == 'O'){
    9.                 bfs(board, i, board[0].length - 1);
    10.             }
    11.         }
    12.  
    13.         for(int j = 1; j < board[0].length - 1; j++){
    14.             if(board[0][j] == 'O'){
    15.                 bfs(board, 0, j);
    16.             }
    17.             if(board[board.length - 1][j] == 'O'){
    18.                 bfs(board, board.length - 1, j);
    19.             }
    20.         }
    21.  
    22.         for(int i = 0; i < board.length; i++){
    23.             for(int j = 0; j < board[0].length; j++){
    24.                 if(board[i][j] == 'A'){
    25.                     board[i][j] = 'O';
    26.                 }else if(board[i][j] == 'O'){
    27.                     board[i][j] = 'X';
    28.                 }
    29.             }
    30.         }
    31.     }
    32.  
    33.     public void bfs(char[][] board, int i, int j){
    34.         Queue<int[]> queue = new LinkedList<>();
    35.         queue.offer(new int[]{i, j});
    36.         while(!queue.isEmpty()){
    37.             int[] cur = queue.poll();
    38.             i = cur[0];
    39.             j = cur[1];
    40.             if(i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == 'O'){
    41.                 board[i][j] = 'A';
    42.                 queue.offer(new int[]{i - 1, j});
    43.                 queue.offer(new int[]{i + 1, j});
    44.                 queue.offer(new int[]{i, j - 1});
    45.                 queue.offer(new int[]{i, j + 1});
    46.             }
    47.         }
    48.     }
    49. }

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

    有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

    1. // dfs
    2. class Solution {
    3.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    4.  
    5.     public List> pacificAtlantic(int[][] heights) {
    6.         int m = heights.length;
    7.         int n = heights[0].length;
    8.         boolean[][] pacific = new boolean[m][n];
    9.         boolean[][] atlantic = new boolean[m][n];
    10.  
    11.         for(int i = 0; i < m; i++){
    12.             dfs(heights, pacific, i, 0);
    13.             dfs(heights, atlantic, i, n - 1);
    14.         }
    15.         for(int j = 0; j < n; j++){
    16.             dfs(heights, pacific, 0, j);
    17.             dfs(heights, atlantic, m - 1, j);
    18.         }
    19.  
    20.         List> list = new ArrayList<>();
    21.         for(int i = 0; i < m; i++){
    22.             for(int j = 0; j < n; j++){
    23.                 if(pacific[i][j] && atlantic[i][j]){
    24.                     list.add(new ArrayList<>(Arrays.asList(i, j)));
    25.                 }
    26.             }
    27.         }
    28.         return list;
    29.     }
    30.  
    31.     public void dfs(int[][] heights, boolean[][] ocean, int i, int j){
    32.         if(ocean[i][j]){
    33.             return;
    34.         }
    35.  
    36.         ocean[i][j] = true;
    37.         for(int[] pos : positions){
    38.             int newRow = i + pos[0];
    39.             int newColumn = j + pos[1];
    40.             if(newRow < 0 || newRow >= heights.length || newColumn < 0 || newColumn >= heights[0].length || heights[i][j] > heights[newRow][newColumn]){
    41.                 continue;
    42.             }
    43.             dfs(heights, ocean, newRow, newColumn);
    44.         }
    45.     }
    46. }
    1. // bfs
    2. class Solution {
    3.     int[][] positions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    4.  
    5.     public List> pacificAtlantic(int[][] heights) {
    6.         int m = heights.length;
    7.         int n = heights[0].length;
    8.         boolean[][] pacific = new boolean[m][n];
    9.         boolean[][] atlantic = new boolean[m][n];
    10.  
    11.         for(int i = 0; i < m; i++){
    12.             bfs(heights, pacific, i, 0);
    13.             bfs(heights, atlantic, i, n - 1);
    14.         }
    15.         for(int j = 0; j < n; j++){
    16.             bfs(heights, pacific, 0, j);
    17.             bfs(heights, atlantic, m - 1, j);
    18.         }
    19.  
    20.         List> list = new ArrayList<>();
    21.         for(int i = 0; i < m; i++){
    22.             for(int j = 0; j < n; j++){
    23.                 if(pacific[i][j] && atlantic[i][j]){
    24.                     list.add(new ArrayList<>(Arrays.asList(i, j)));
    25.                 }
    26.             }
    27.         }
    28.         return list;
    29.     }
    30.  
    31.     public void bfs(int[][] heights, boolean[][] ocean, int i, int j){
    32.         ocean[i][j] = true;
    33.         Queue<int[]> queue = new LinkedList<>();
    34.         queue.offer(new int[]{i, j});
    35.         while(!queue.isEmpty()){
    36.             int[] cur = queue.poll();
    37.             for(int[] pos : positions){
    38.                 int newRow = cur[0] + pos[0];
    39.                 int newColumn = cur[1] + pos[1];
    40.                 if(newRow < 0 || newRow >= heights.length || newColumn < 0 || newColumn >= heights[0].length || heights[cur[0]][cur[1]] > heights[newRow][newColumn] || ocean[newRow][newColumn]){
    41.                     continue;
    42.                 }
    43.                 ocean[newRow][newColumn] = true;
    44.                 queue.offer(new int[]{newRow, newColumn});
    45.             }
    46.         }
    47.     }
    48. }

    841. 钥匙和房间

    有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

    示例1：输入：rooms = [[1],[2],[3],[]]         输出：true

    示例2：输入：rooms = [[1,3],[3,0,1],[2],[0]]         输出：false

    1. // dfs
    2. class Solution {
    3.     public boolean canVisitAllRooms(List> rooms) {
    4.         boolean[] visited = new boolean[rooms.size()];
    5.         dfs(rooms, visited, 0);
    6.         for(int i = 0; i < visited.length; i++){
    7.             if(!visited[i]){
    8.                 return false;
    9.             }
    10.         }
    11.         return true;
    12.     }
    13.  
    14.     public void dfs(List> rooms, boolean[] visited, int key){
    15.         if(visited[key]){
    16.             return;
    17.         }
    18.  
    19.         visited[key] = true;
    20.         List curRoom = rooms.get(key);
    21.         for(int i = 0; i < curRoom.size(); i++){
    22.             dfs(rooms, visited, curRoom.get(i));
    23.         }
    24.     }
    25. }
    1. // bfs
    2. class Solution {
    3.     public boolean canVisitAllRooms(List> rooms) {
    4.         boolean[] visited = new boolean[rooms.size()];
    5.         bfs(rooms, visited);
    6.         for(int i = 0; i < visited.length; i++){
    7.             if(!visited[i]){
    8.                 return false;
    9.             }
    10.         }
    11.         return true;
    12.     }
    13.  
    14.     public void bfs(List> rooms, boolean[] visited){
    15.         Queue queue = new LinkedList<>();
    16.         queue.offer(0);
    17.         while(!queue.isEmpty()){
    18.             int curKey = queue.poll();
    19.             visited[curKey] = true;
    20.             List curRoom = rooms.get(curKey);
    21.             for(int i = 0; i < curRoom.size(); i++){
    22.                 if(visited[curRoom.get(i)]){
    23.                     continue;
    24.                 }
    25.                 queue.offer(curRoom.get(i));
    26.             }
    27.         }
    28.     }
    29. }

    127. 单词接龙

    字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：①每一对相邻的单词只差一个字母；②对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中；③sk == endWord。给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

    示例：输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]         输出：5；

    解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

    1. class Solution {
    2.     public int ladderLength(String beginWord, String endWord, List wordList) {
    3.         Set wordSet = new HashSet<>(wordList);  // 转换为HashSet, 加快速度
    4.         if(!wordSet.contains(endWord)){
    5.             return 0;
    6.         }
    7.  
    8.         // bfs  广搜只要搜到了终点，那么一定是最短的路径
    9.         Queue queue = new LinkedList<>();
    10.         queue.offer(beginWord);
    11.         Map map = new HashMap<>();  // 存储单词对应的路径长度
    12.         map.put(beginWord, 1);
    13.  
    14.         while(!queue.isEmpty()){
    15.             String word = queue.poll();
    16.             int pathLen = map.get(word);
    17.             for(int i = 0; i < word.length(); i++){
    18.                 char[] chars = word.toCharArray();
    19.                 for(char j = 'a'; j <= 'z'; j++){
    20.                     chars[i] = j;
    21.                     String newWord = String.valueOf(chars);
    22.                     if(newWord.equals(endWord)){
    23.                         return pathLen + 1;
    24.                     }
    25.                     if(wordSet.contains(newWord) && !map.containsKey(newWord)){
    26.                         queue.offer(newWord);
    27.                         map.put(newWord, pathLen + 1);
    28.                     }
    29.                 }
    30.             }
    31.         }
    32.         return 0;
    33.     }
    34. }
  • 相关阅读:
    高光谱遥感学习入门丨高光谱数据处理基础、Python和Matlab高光谱遥感数据处理
    aspnetcore6.0源代码编译调试
    EventSystem 事件系统
    spring复习：（60）自定义qualifier
    GoLand 2023：为Go开发者打造的智能IDE mac/win激活版
    IMX6ULL学习笔记（4）——安装并使用交叉编译工具链
    JAVA计算机毕业设计食堂综合评价系统源码+系统+mysql数据库+lw文档
    代码审计之路之白盒挖掘机 | 技术精选01
    MySQL索引
    我的创作纪念日—小梁说代码
  • 原文地址：https://blog.csdn.net/Archer__13/article/details/133933033