Day52--图论--101. 孤岛的总面积（卡码网），102. 沉没孤岛（卡码网），103. 水流问题（卡码网），104. 建造最大岛屿（卡码网）

方法：深搜

思路：

dfs函数返回值设为布尔值，只要岛屿的任意节点接触到边框，向上返回false。

每座岛屿都是从主函数进入的，所以在主函数中进行判断与加和操作。岛屿的节点全部是true，才能视为孤岛，加入到总面积。

import java.util.*;public class Main {private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};private static int count = 0;private static boolean dfs(int[][] grid, boolean[][] visited, int x, int y) {// 岛屿面积++count++;// 孤岛标志，布尔变量boolean isolate = true;// 如果该岛接触到边框了，孤岛标志为falseif (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1) {isolate = false;}for (int i = 0; i < dir.length; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;boolean nextFlag = dfs(grid, visited, nextX, nextY);// 如果深搜的过程中，本岛的任何节点接触到边框，本岛都不再是孤岛// 进行与操作,只有每个节点都true,才能是孤岛isolate = isolate && nextFlag;}}return isolate;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = in.nextInt();}}boolean[][] visited = new boolean[n][m];int totalArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;// 因为是全局变量，所以每遇到一座岛，count归零count = 0;boolean isolate = dfs(grid, visited, i, j);// 确定是孤岛，再加入到总面积if (isolate) {totalArea += count;}}}}System.out.println(totalArea);}
}

方法：深搜

思路：

第一步找到孤岛。

第二步，从同一个入口进去，再深搜一遍，因为是孤岛，所以四周要么就是visited为true，要么就是水，所以把能深搜到的visited为true的节点全部沉没。

import java.util.*;public class Main {private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};// 判断孤岛private static boolean dfs(int[][] grid, boolean[][] visited, int x, int y) {// 孤岛标志，布尔变量boolean isolate = true;// 如果该岛接触到边框了，孤岛标志为falseif (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1) {isolate = false;}for (int i = 0; i < dir.length; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;boolean nextFlag = dfs(grid, visited, nextX, nextY);// 如果深搜的过程中，本岛的任何节点接触到边框，本岛都不再是孤岛// 进行与操作,只有每个节点都true,才能是孤岛isolate = isolate && nextFlag;}}return isolate;}// 沉没孤岛private static void dfsDown(int[][] grid, boolean[][] visited, int x, int y) {grid[x][y] = 0;for (int i = 0; i < dir.length; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 注意这里不再是!visited了// 因为是孤岛，所以四周要么就是visited为true，要么就是水，所以不怕越界，大胆沉没if (visited[nextX][nextY] && grid[nextX][nextY] == 1) {dfsDown(grid, visited, nextX, nextY);}}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = in.nextInt();}}boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;boolean isolate = dfs(grid, visited, i, j);// 确定是孤岛，将孤岛沉没if (isolate) {dfsDown(grid, visited, i, j);}}}}print(grid);}private static void print(int[][] grid) {for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {System.out.print(grid[i][j] + " ");}System.out.println();}}
}

方法：深搜

思路：

如果顺序执行，那么每个节点O(mn)都要进行深搜O(mn)，就是O(n⁴)的时间复杂度。

所以反过来想问题。从边界出发，能够走到的最高点是哪里？

标记从左边，上边出发的点，能够遍历到的最大高度。

标记从右边，下边出发的店，能够遍历到的最大高度。

二者都标记过的，就是说明，该高度的水，可以同时流到两组的边界。

import java.util.*;public class Main {// 方向标private static final int[][] dir = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };// 深搜static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 递归终止条件// 这次写在进入dfs之后，而不是dfs之前，是因为要进dfs的地方太多了，写在这里就一次if (visited[x][y]) {return;}visited[x][y] = true;for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 注意：这里是从低向高遍历if (!visited[nextX][nextY] && grid[x][y] <= grid[nextX][nextY]) {dfs(grid, visited, nextX, nextY);}}}// 主函数public static void main(String[] args) {// 录入数据Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}// 标记从第一组边界上的节点出发，可以遍历的节点boolean[][] firstBorder = new boolean[n][m];// 标记从第二组边界上的节点出发，可以遍历的节点boolean[][] secondBorder = new boolean[n][m];for (int i = 0; i < n; i++) {// 左边界出发，向高处遍历dfs(grid, firstBorder, i, 0);// 右边界出发dfs(grid, secondBorder, i, m - 1);}for (int j = 0; j < m; j++) {// 上边界出发dfs(grid, firstBorder, 0, j);// 下边界出发dfs(grid, secondBorder, n - 1, j);}// 打印输出for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果if (firstBorder[i][j] && secondBorder[i][j]) {System.out.println(i + " " + j);}}}}
}

这道题，理解起来不难，但是要做的时候步骤很多，而且很多细节的问题需要把控到。

最关键的地方：每完成一个步骤，把对应的矩阵打印出来看，看看是否达到自己的设定。

方法：深搜

思路：

1. 第一次深搜：给岛屿编号，并找到该岛屿的总面积
   • 深搜后，grid矩阵，记录岛屿的编号
   • 岛屿的总面积为count
   • 每一个遍历过的节点，把对应的area矩阵的位置，设为-1，待会要用
2. 第二次深搜：在刚才的节点再进去深搜一遍，在area矩阵，每个节点都记录整个岛屿的面积
   • 深搜的时候，因为visited数组已经被用过了，要再想深搜退出的条件，不能再是!visited了——每进一层深搜，变化的是什么呢？area值。所以当area值是-1的节点，就进去，area为0或者已经有值的节点，不进去。
   • 深搜后，area矩阵，每个节点都记录整个岛屿的面积
3. 遍历每个水节点，假设当前水节点变为陆地之后，总面积为temp
   • 检查水节点的上下左右节点。
   • 每个节点，都要先检查编号，是否是同一个岛屿（使用set），如果不是同一个岛屿，area面积加入到temp中
4. 最后，检查maxArea是否为0。如果仍是0，证明给出的矩阵，全是陆地，没有任何水，返回陆地的面积n*m

import java.util.*;public class Main {// 方向标private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};// 面积计数器private static int count = 0;// 岛屿编号private static int islandNumber = 0;// 深搜，找到岛屿并编号private static void dfs(int[][] grid, boolean[][] visited, int[][] area, int x, int y) {// 岛屿面积+1count++;// 岛屿编号设定grid[x][y] = islandNumber;// 设定面积的时候要用的判定条件；第一次深搜的时候，将节点面积设为-1area[x][y] = -1;// 常规的深搜for (int i = 0; i < dir.length; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (!visited[nextX][nextY] && grid[nextX][nextY] != 0) {visited[nextX][nextY] = true;dfs(grid, visited, area, nextX, nextY);}}}// 深搜，设置岛屿面积private static void setArea(int[][] grid, boolean[][] visited, int[][] area, int x, int y) {// 设定岛屿面积area[x][y] = count;// 常规的深搜for (int i = 0; i < dir.length; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 在第一次深搜的时候，岛屿每个节点的面积为-1// 这是第二次深搜，每设定一个节点，该节点的面积就不可能是-1// area从-1变成count。这里起到一个visited=true的标记作用。if (area[nextX][nextY] < 0 && grid[nextX][nextY] != 0) {setArea(grid, visited, area, nextX, nextY);}}}// 主函数public static void main(String[] args) {// 录入题目数据Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = in.nextInt();}}// 标记数组,第一遍深搜用boolean[][] visited = new boolean[n][m];// 面积数组,记录每个节点所在岛屿的面积int[][] area = new int[n][m];// 第一第二次深搜,找到岛屿,标记岛屿编号,设定岛屿面积for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 因为设定标号的时候,直接在grid上操作了,所以这里不能再用grid[i][j] == 1if (!visited[i][j] && grid[i][j] != 0) {// 每到这里,都是一个新的岛屿,所以count=0count = 0;// 岛屿编号+1islandNumber++;// 第一次深搜visited[i][j] = true;dfs(grid, visited, area, i, j);// 第二次深搜:设定岛屿面积setArea(grid, visited, area, i, j);}}}// 遍历每个水,开始将某个水节点设为变为陆地int maxArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 遍历水if (grid[i][j] == 0) {// 要用set记录陆地的编号Set<Integer> set = new HashSet<>();// 本节点(水)的面积为1int temp = 1;// 水的四周节点// 上if (i > 0) {// 把编号加到set中set.add(grid[i - 1][j]);temp += area[i - 1][j];}// 左if (j > 0) {// 检查与上是否是同一个岛屿编号if (!set.contains(grid[i][j - 1])) {temp += area[i][j - 1];// 把编号加到set中set.add(grid[i][j - 1]);}}// 下if (i < grid.length - 1) {if (!set.contains(grid[i + 1][j])) {temp += area[i + 1][j];set.add(grid[i + 1][j]);}}// 右if (j < grid[0].length - 1) {if (!set.contains(grid[i][j + 1])) {temp += area[i][j + 1];}}// 刷新最大面积maxArea = Math.max(maxArea, temp);}}}// 最后,要判断maxArea是否为0,如果仍是0,证明给出的矩阵,全是陆地,没有任何水,返回陆地的面积System.out.println(maxArea == 0 ? n * m : maxArea);// print(area);}// 打印grid或者area来检查private static void print(int[][] grid) {for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {System.out.print(grid[i][j] + " ");}System.out.println();}}
}

这道题踩了很多坑。第一次提交的时候，矩阵全是陆地，返回面积错误；第二次提交的时候，没有用编号和set区分岛屿，水的四周其实是同一座岛屿，返回面积错误。