图论part3｜101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题

101. 孤岛的总面积

• 🔗：101. 孤岛的总面积
• 思路：和昨天的岛的区别是：是否有挨着边的岛屿
  • 所以可以先遍历四条边挨着的岛屿，把他们标记为非孤岛
  • 再计算其他岛屿当中的最大面积
• 代码：（深度搜索）

• import java.util.*;
  /*思路：和岛的区别是：是否有挨着边的岛屿--所以可以先遍历四条边挨着的岛屿，把他们标记为非孤岛--再计算其他岛屿当中的最大面积
  */
  public class Main{public static int count = 0;public static void dfs(int[][] matrix,int i,int j, int aim){// 终止条件if(i>=matrix.length || i<0 || j<0 || j>=matrix[0].length) return;if(matrix[i][j]!=1) return;// markmatrix[i][j] = aim;count++;// 遍历dfs(matrix, i, j-1, aim);dfs(matrix, i, j+1, aim);dfs(matrix, i-1, j, aim);dfs(matrix, i+1, j, aim);}public static void main(String[] args){// N MScanner scanner = new Scanner(System.in);int row = scanner.nextInt();int col = scanner.nextInt();int[][] matrix = new int [row][col];for(int i=0; i<row; i++){for(int j=0; j<col; j++){matrix[i][j] = scanner.nextInt();}}// dfsfor(int i=0; i<row; i++){if(matrix[i][0]==1)dfs(matrix, i, 0, 2);if(matrix[i][col-1]==1)dfs(matrix, i, col-1,2);}for(int j=0; j<col; j++){if(matrix[0][j]==1)dfs(matrix,0,j,2);if(matrix[row-1][j] == 1)dfs(matrix,row-1,j,2);}count=0;for(int i=1; i<row; i++){for(int j=1; j<col; j++){if(matrix[i][j]==1){dfs(matrix, i, j, 3);}}}System.out.println(count);}}

• 代码：广度搜索

import java.util.*;
/*思路：和岛的区别是：是否有挨着边的岛屿--所以可以先遍历四条边挨着的岛屿，把他们标记为非孤岛--再计算其他岛屿当中的最大面积
*/
public class Main{public static int count = 0;private static final int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};public static void bfs(int[][] matrix,int r,int c, int aim){// queue, linkedlist// method: poll. add. isEmptyQueue<int[]> que = new LinkedList<>();que.add(new int[]{r,c});matrix[r][c] = aim;count++;while(!que.isEmpty()){int[] cur = que.poll();int row = cur[0];int col = cur[1];for(int i=0; i<4; i++){int nr = row + dir[i][0];int nc = col + dir[i][1];if(nr<0||nc<0||nr>=matrix.length||nc>=matrix[0].length)continue;if(matrix[nr][nc]==1){que.add(new int[]{nr,nc});count++;matrix[nr][nc] = aim;}}}}public static void main(String[] args){// N MScanner scanner = new Scanner(System.in);int row = scanner.nextInt();int col = scanner.nextInt();int[][] matrix = new int [row][col];for(int i=0; i<row; i++){for(int j=0; j<col; j++){matrix[i][j] = scanner.nextInt();}}// bfsfor(int i=0; i<row; i++){if(matrix[i][0]==1)bfs(matrix, i, 0, 2);if(matrix[i][col-1]==1)bfs(matrix, i, col-1,2);}for(int j=0; j<col; j++){if(matrix[0][j]==1)bfs(matrix,0,j,2);if(matrix[row-1][j] == 1)bfs(matrix,row-1,j,2);}count=0;for(int i=1; i<row; i++){for(int j=1; j<col; j++){if(matrix[i][j]==1){bfs(matrix, i, j, 3);}}}System.out.println(count);}}

102. 沉没孤岛

• 🔗：102. 沉没孤岛
• 思路：感受不到和上一题太大的区别
• 代码：（dfs）

  • import java.util.*;
    /*思路：*/
    public class Main{public static void dfs(int[][] matrix,int i,int j, int aim){// 终止条件if(i>=matrix.length || i<0 || j<0 || j>=matrix[0].length) return;if(matrix[i][j]!=1) return;// markmatrix[i][j] = aim;// 遍历dfs(matrix, i, j-1, aim);dfs(matrix, i, j+1, aim);dfs(matrix, i-1, j, aim);dfs(matrix, i+1, j, aim);}public static void main(String[] args){// N MScanner scanner = new Scanner(System.in);int row = scanner.nextInt();int col = scanner.nextInt();int[][] matrix = new int [row][col];for(int i=0; i<row; i++){for(int j=0; j<col; j++){matrix[i][j] = scanner.nextInt();}}// dfsfor(int i=0; i<row; i++){if(matrix[i][0]==1)dfs(matrix, i, 0, 2);if(matrix[i][col-1]==1)dfs(matrix, i, col-1,2);}for(int j=0; j<col; j++){if(matrix[0][j]==1)dfs(matrix,0,j,2);if(matrix[row-1][j] == 1)dfs(matrix,row-1,j,2);}for(int i=0; i<row; i++){for(int j=0; j<col; j++){if(matrix[i][j] == 2)System.out.print(1+" ");elseSystem.out.print(0 + " "); }System.out.print("\n");}}

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

• 🔗：
  417. 太平洋大西洋水流问题https://leetcode.cn/problems/pacific-atlantic-water-flow/
• 思路：
  • 这一题题目有一点难以理解，当时大体上有了前两题的铺垫还是比较好做的。
  • 题意大概是：左上两条边连接pacific，右下两条边连接Atlantic，雨水可以流向小于等于高度的方向（东南西北），求同时可以流向太平洋和大西洋的方块。
  • 这题可以分成两部分来看，首先找到可以流向pacific的点，然后找到可以流向Atlantic的点，求它们的交集。
    • 存储方式：我一开始想到的是用三维数组进行存储，当时两个二维数组的方式可能更好写一些（没有太大区别）
  • 遍历方式：采用深度优先遍历，遍历过的点都设置为true（有一点像岛屿问题），如果不能延伸则return（返回条件，即相邻岛屿高度<目前岛屿高度）
• 代码：

  • class Solution {static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};int[][] heights;int m,n;public List<List<Integer>> pacificAtlantic(int[][] heights) {this.heights = heights;this.m = heights.length;this.n = heights[0].length;boolean[][] pacific = new boolean[m][n];boolean[][] atlantic = new boolean[m][n];for(int i=0; i<m; i++){dfs(i, 0, pacific);}    for(int i=0; i<m; i++){dfs(i, n-1, atlantic);}for(int j=1; j<n;j++){dfs(0,j,pacific);}           for(int j=0; j<n-1; j++){dfs(m-1,j,atlantic);}List<List<Integer>> result = new ArrayList<>();for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(pacific[i][j] && atlantic[i][j]){List<Integer> cell = new ArrayList<>();cell.add(i);cell.add(j);result.add(cell);}}}return result;}public void dfs(int row, int col, boolean[][] ocean){if(ocean[row][col]) return;ocean[row][col] = true;for(int[] dir:dirs){int newRow = row + dir[0];int newCol = col + dir[1];if(newRow>=0 && newCol>=0 && newRow<m && newCol<n && heights[newRow][newCol]>=heights[row][col]){dfs(newRow, newCol, ocean);}}}
    }