图论③ | Java | 孤岛的总面积、沉没孤岛、水流问题 、建造最大岛屿

101. 孤岛的总面积

卡玛 101. 孤岛的总面积
https://kamacoder.com/problempage.php?pid=1173

孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

• 从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋
  

import java.util.*;class Main {static int count;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grid = new int[n][m];for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {grid[i][j] = sc.nextInt();}}// 从左侧边，和右侧边向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 从上边和下边向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) dfs(grid, i, j);}}System.out.println(count);}public static void dfs(int[][]grid, int x, int y){if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]!=1) {return;}grid[x][y] = 0;count++;int[] di = {0,0,-1,1};int[] dj = {1,-1,0,0};for(int index=0; index<4; index++) {int next_i = x + di[index];int next_j = y + dj[index];dfs(grid, next_i, next_j);}}
}

102.沉没孤岛

103.水流问题

力扣 太平洋大西洋水流问题 417
https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

class Solution {int m, n;static int[] di = {0,0,1,-1};static int[] dj = {1,-1,0,0};int[][] heights;public List<List<Integer>> pacificAtlantic(int[][] heights) {List<List<Integer>> result = new ArrayList<List<Integer>>();//从边界开始 上升this.heights = heights;this.m = heights.length;this.n = heights[0].length;boolean[][] pacific = new boolean[m][n]; // 默认值是falseboolean[][] atlantic = new boolean[m][n];for (int i = 0; i < m; i++) {dfs(i, 0, pacific);}for (int j = 1; j < n; j++) {dfs(0, j, pacific);}for (int i = 0; i < m; i++) {dfs(i, n - 1, atlantic);}for (int j = 0; j < n - 1; j++) {dfs(m - 1, j, atlantic);}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<Integer>();cell.add(i);cell.add(j);result.add(cell);}}}return result;}public void dfs(int x, int y, boolean[][]ocean){if(ocean[x][y]) { //这个区域已经访问过了return;}ocean[x][y] = true;for(int i=0; i<4; i++) {int next_i = x + di[i];int next_j = y + dj[i];if(next_i>=0 && next_i<m && next_j>=0 && next_j<n && heights[next_i][next_j] >= heights[x][y]){dfs(next_i, next_j, ocean);}}}
}

104.建造最大岛屿

没有思路

• 来自代码随想录 思路
  暴力想法，遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。
  每改变一个0的方格，都需要重新计算一个地图的最大面积，所以 整体时间复杂度为：n^4。

• 优化思路
  第一次遍历：把每一个孤岛的面积都求出来，并且存在一个 HashMap中。（孤岛编号，孤岛面积）
  第二次：遍历每个 grid[i][j]=0 ，也就是遍历每一个“海洋”，当把它设置为1的时候，并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

• 代码来自代码随想录

public class Main {// 该方法采用 DFS// 定义全局变量// 记录每次每个岛屿的面积static int count;// 对每个岛屿进行标记static int mark;// 定义二维数组表示四个方位static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};// DFS 进行搜索，将每个岛屿标记为不同的数字public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {// 当遇到边界，直接returnif (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;// 遇到已经访问过的或者遇到海水，直接返回if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true;count++;grid[x][y] = mark;// 继续向下层搜索dfs(grid, x, y + 1, visited);dfs(grid, x, y - 1, visited);dfs(grid, x + 1, y, visited);dfs(grid, x - 1, y, visited);}public static void main (String[] args) {// 接收输入Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}// 初始化mark变量，从2开始（区别于0水，1岛屿）mark = 2;// 定义二位boolean数组记录该位置是否被访问boolean[][] visited = new boolean[n][m];// 定义一个HashMap，记录某片岛屿的标记号和面积HashMap<Integer, Integer> getSize = new HashMap<>();// 定义一个HashSet，用来判断某一位置水四周是否存在不同标记编号的岛屿HashSet<Integer> set = new HashSet<>();// 定义一个boolean变量，看看DFS之后，是否全是岛屿boolean isAllIsland = true;// 遍历二维数组进行DFS搜索，标记每片岛屿的编号，记录对应的面积for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) isAllIsland = false;if (grid[i][j] == 1) {count = 0;dfs(grid, i, j, visited);getSize.put(mark, count);mark++;}}}int result = 0;if (isAllIsland) result =  m * n;// 对标记完的grid继续遍历，判断每个水位置四周是否有岛屿，并记录下四周不同相邻岛屿面积之和// 每次计算完一个水位置周围可能存在的岛屿面积之和，更新下result变量for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) {set.clear();// 当前水位置变更为岛屿，所以初始化为1int curSize = 1;for (int[] dir : dirs) {int curRow = i + dir[0];int curCol = j + dir[1];if (curRow < 0 || curRow >= n || curCol < 0 || curCol >= m) continue;int curMark = grid[curRow][curCol];// 如果当前相邻的岛屿已经遍历过或者HashMap中不存在这个编号，继续搜索if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;set.add(curMark);curSize += getSize.get(curMark);}result = Math.max(result, curSize);}}}// 打印结果System.out.println(result);}
}