代码随想录算法训练营第五十二天 | Carl101-孤岛的总面积、Carl102-沉没孤岛、Carl103-水流问题、Carl104-建造最大岛屿
Carl101 孤岛的总面积
题目链接：https://kamacoder.com/problempage.php?pid=1173
文章讲解：https://www.programmercarl.com/kamacoder/0101.孤岛的总面积.html
视频讲解：https://www.bilibili.com/video/BV1mmZJYRESc/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本质上就是在“Carl100 岛屿的最大面积”的基础上，增加了边界岛屿面积不计的要求，在累加总面积之前，单独遍历四条边界，对靠地图四边的岛屿进行标记但不累加计数即可
import java.util.*;public class Main{static int result = 0;static int curArea = 0;static int rowNum = 0;static int colNum = 0;static int[][] direction = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};public static void dfs(int[][] graph, boolean[][] visited, int x, int y){for(int i = 0; i < 4; i++){int nextX = x + direction[i][0];int nextY = y + direction[i][1];if(nextX < 0 || nextX >= rowNum || nextY < 0 || nextY >= colNum){continue;}if(graph[nextX][nextY] == 1 && !visited[nextX][nextY]){curArea++;visited[nextX][nextY] = true;dfs(graph, visited, nextX, nextY);}}}public static void main(String[] args){Scanner scan = new Scanner(System.in);rowNum = scan.nextInt();colNum = scan.nextInt();int[][] graph = new int[rowNum][colNum];for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){graph[i][j] = scan.nextInt();}}boolean[][] visited = new boolean[rowNum][colNum];for(int j = 0; j < colNum; j++){if(graph[0][j] == 1 && !visited[0][j]){visited[0][j] = true;dfs(graph, visited, 0, j);}if(graph[rowNum-1][j] == 1 && !visited[rowNum-1][j]){visited[rowNum-1][j] = true;dfs(graph, visited, rowNum-1, j);}}for(int i = 1; i < rowNum-1; i++){if(graph[i][0] == 1 && !visited[i][0]){visited[i][0] = true;dfs(graph, visited, i, 0);}if(graph[i][colNum-1] == 1 && !visited[i][colNum-1]){visited[i][colNum-1] = true;dfs(graph, visited, i, colNum-1);}}for(int i = 1; i < rowNum-1; i++){for(int j = 1; j < colNum-1; j++){if(graph[i][j] == 1 && !visited[i][j]){curArea = 1;visited[i][j] = true;dfs(graph, visited, i, j);result += curArea;}}}System.out.println(result);}
}
Carl102 沉没孤岛
题目链接：https://kamacoder.com/problempage.php?pid=1174
文章讲解：https://www.programmercarl.com/kamacoder/0102.沉没孤岛.html
视频讲解：https://www.bilibili.com/video/BV1fjdWYyEGu?vd_source=b989f2b109eb3b17e8178154a7de7a51&spm_id_from=333.788.videopod.sections
先扫描四条边界，用DFS对与边界相接的岛屿用2标记，接着两层for循环遍历整个图，遇到1就化为0，遇到2就化为1
import java.util.*;public class Main{static int rowNum = 0;static int colNum = 0;static int[][] direction = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};public static void dfs(int[][] graph, int x, int y){for(int i = 0; i < 4; i++){int nextX = x + direction[i][0];int nextY = y + direction[i][1];if(nextX < 0 || nextX >= rowNum || nextY < 0 || nextY >= colNum) continue;if(graph[nextX][nextY] == 1){graph[nextX][nextY] = 2;dfs(graph, nextX, nextY);}}}public static void main(String[] args){Scanner scan = new Scanner(System.in);rowNum = scan.nextInt();colNum = scan.nextInt();int[][] graph = new int[rowNum][colNum];for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){graph[i][j] = scan.nextInt();}}for(int j = 0; j < colNum; j++){if(graph[0][j] == 1){graph[0][j] = 2;dfs(graph, 0, j);}if(graph[rowNum-1][j] == 1){graph[rowNum-1][j] = 2;dfs(graph, rowNum-1, j);}}for(int i = 1; i < rowNum-1; i++){if(graph[i][0] == 1){graph[i][0] = 2;dfs(graph, i, 0);}if(graph[i][colNum-1] == 1){graph[i][colNum-1] = 2;dfs(graph, i, colNum-1);}}for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){if(graph[i][j] == 1) graph[i][j] = 0;if(graph[i][j] == 2) graph[i][j] = 1;}}for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){System.out.print(graph[i][j] + " ");}System.out.println();}}
}
Carl103 水流问题
题目链接：https://kamacoder.com/problempage.php?pid=1175
文章讲解：https://www.programmercarl.com/kamacoder/0103.水流问题.html
视频讲解：https://www.bilibili.com/video/BV1WNoEYrEio?vd_source=b989f2b109eb3b17e8178154a7de7a51&spm_id_from=333.788.videopod.sections
逆向思维，由两组边界开始，使用DFS分别往中间从小往大遍历，被两组边界同时标记的格子，就是满足题目要求的格子
import java.util.*;public class Main{static int rowNum = 0;static int colNum = 0;static int[][] direction = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};public static void dfs(int[][] graph, boolean[][] visited, int x, int y){if(visited[x][y]) return;visited[x][y] = true;for(int i = 0; i < 4; i++){int nextX = x + direction[i][0];int nextY = y + direction[i][1];if(nextX < 0 || nextX >= rowNum || nextY < 0 || nextY >= colNum){continue;}if(graph[nextX][nextY] >= graph[x][y]){dfs(graph, visited, nextX, nextY);}}}public static void main(String[] args){Scanner scan = new Scanner(System.in);rowNum = scan.nextInt();colNum = scan.nextInt();int[][] graph = new int[rowNum][colNum];for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){graph[i][j] = scan.nextInt();}}boolean[][] firstBorder = new boolean[rowNum][colNum];boolean[][] secondBorder = new boolean[rowNum][colNum];for(int i = 0; i < rowNum; i++){dfs(graph, firstBorder, i, 0);dfs(graph, secondBorder, i, colNum-1);}for(int j = 0; j < colNum; j++){dfs(graph, firstBorder, 0, j);dfs(graph, secondBorder, rowNum-1, j);}for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){if(firstBorder[i][j] && secondBorder[i][j]){System.out.println(i + " " + j);}}}}
}
Carl104 建造最大岛屿
题目链接：https://kamacoder.com/problempage.php?pid=1176
文章讲解：https://www.programmercarl.com/kamacoder/0104.建造最大岛屿.html
视频讲解：https://www.bilibili.com/video/BV1Dn5CzZEw1/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这题思路上还算清晰，在具体代码实现上有很多细节需要注意
正常遍历一次地图，用DFS得出各个岛屿的面积，并分别做编号记录，用HashMap记录各个编号对应岛屿的面积，key为岛的编号，value为岛屿面积；然后再遍历地图，遍历0的方格，并统计该方格的周围岛屿面积，将其相邻岛屿的面积相加在一起，遍历所有0之后就可以得出“选一个0变成1”之后的最大面积
在计算0四周岛屿面积的时候，要注意不要重复计算相同岛屿，因此需要HashSet来记录已累加面积的岛屿。在计算下一个0四周岛屿面积之前，记得将HashSet清空
import java.util.*;public class Main{static int rowNum = 0;static int colNum = 0;static int curArea = 0;static int maxArea = 1;static int mark = 2;static boolean isAllIsland = true;static int[][] direction = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};public static void dfs(int[][] graph, int x, int y){for(int i = 0; i < 4; i++){int nextX = x + direction[i][0];int nextY = y + direction[i][1];if(nextX < 0 || nextX >= rowNum || nextY < 0 || nextY >= colNum) continue;if(graph[nextX][nextY] == 1){graph[nextX][nextY] = mark;curArea++;dfs(graph, nextX, nextY);}}}public static void main(String[] args){Scanner scan = new Scanner(System.in);rowNum = scan.nextInt();colNum = scan.nextInt();int[][] graph = new int[rowNum][colNum];for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){graph[i][j] = scan.nextInt();}}HashMap<Integer, Integer> areaMap = new HashMap<>();for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){if(graph[i][j] == 1){curArea = 1;graph[i][j] = mark;dfs(graph, i, j);areaMap.put(mark, curArea);mark++;}if(graph[i][j] == 0){isAllIsland = false;}}}if(isAllIsland){System.out.println(areaMap.get(mark-1));return;}HashSet<Integer> visited = new HashSet<>();for(int i = 0; i < rowNum; i++){for(int j = 0; j < colNum; j++){if(graph[i][j] == 0){curArea = 1;for(int k = 0; k < 4; k++){int nearI = i + direction[k][0];int nearJ = j + direction[k][1];if(nearI < 0 || nearI >= rowNum || nearJ < 0 || nearJ >= colNum) continue;if(graph[nearI][nearJ] != 0 && !visited.contains(graph[nearI][nearJ])){curArea += areaMap.get(graph[nearI][nearJ]);visited.add(graph[nearI][nearJ]);}}maxArea = Math.max(maxArea, curArea);}visited.clear();}}System.out.println(maxArea);}
}