代码随想录-图论Part3101、孤岛的总面积package test.java; import java.util.*; public class dfsPart3 { private static int count 0; private static final int[][] dir {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; private static void bfs(int[][] grid, int x, int y) { Queueint[] que new LinkedList(); que.add(new int[]{x, y}); grid[x][y] 0; // 只要加入队列立刻标记 count; while (!que.isEmpty()) { int[] cur que.poll(); int curx cur[0]; int cury cur[1]; for (int i 0; i 4; i) { int nextx curx dir[i][0]; int nexty cury dir[i][1]; if (nextx 0 || nextx grid.length || nexty 0 || nexty grid[0].length) continue; // 越界了直接跳过 if (grid[nextx][nexty] 1) { que.add(new int[]{nextx, nexty}); count; grid[nextx][nexty] 0; // 只要加入队列立刻标记 } } } } 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(); } } // 从左侧边和右侧边向中间遍历 for (int i 0; i n; i) { if (grid[i][0] 1) bfs(grid, i, 0); if (grid[i][m - 1] 1) bfs(grid, i, m - 1); } // 从上边和下边向中间遍历 for (int j 0; j m; j) { if (grid[0][j] 1) bfs(grid, 0, j); if (grid[n - 1][j] 1) bfs(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) bfs(grid, i, j); } } System.out.println(count); scanner.close(); } }102、沉默孤岛package test.java; import java.util.Scanner; public class dfsPart4 { static int[][] dir { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; // 保存四个方向 public static void dfs(int[][] grid, int x, int y) { grid[x][y] 2; for (int[] d : dir) { int nextX x d[0]; int nextY y d[1]; // 超过边界 if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) continue; // 不符合条件不继续遍历 if (grid[nextX][nextY] 0 || grid[nextX][nextY] 2) continue; dfs(grid, 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(); } } // 步骤一 // 从左侧边和右侧边 向中间遍历 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); } // 步骤二、步骤三 for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) grid[i][j] 0; if (grid[i][j] 2) grid[i][j] 1; } } for (int i 0; i n; i) { for (int j 0; j m; j) { System.out.print(grid[i][j] ); } System.out.println(); } scanner.close(); } }103、水流问题这道太难了……后续再练习吧104、建造最大岛屿package test.java; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; public class dfsPart5 { // 该方法采用 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) { // 当遇到边界直接return if (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 m sc.nextInt(); int n sc.nextInt(); int[][] grid new int[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); } } // 初始化mark变量从2开始区别于0水1岛屿 mark 2; // 定义二位boolean数组记录该位置是否被访问 boolean[][] visited new boolean[m][n]; // 定义一个HashMap记录某片岛屿的标记号和面积 HashMapInteger, Integer getSize new HashMap(); // 定义一个HashSet用来判断某一位置水四周是否存在不同标记编号的岛屿 HashSetInteger set new HashSet(); // 定义一个boolean变量看看DFS之后是否全是岛屿 boolean isAllIsland true; // 遍历二维数组进行DFS搜索标记每片岛屿的编号记录对应的面积 for (int i 0; i m; i) { for (int j 0; j n; 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 m; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { set.clear(); // 当前水位置变更为岛屿所以初始化为1 int curSize 1; for (int[] dir : dirs) { int curRow i dir[0]; int curCol j dir[1]; if (curRow 0 || curRow m || curCol 0 || curCol n) 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); sc.close(); } }