欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 新车 > 图论part3|101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题

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

2025/3/15 6:20:08 来源:https://blog.csdn.net/m0_62572567/article/details/146243532  浏览:    关键词:图论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);}}}
      }

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词