Day51--图论--99. 岛屿数量（卡码网），100. 岛屿的最大面积（卡码网）

方法：深搜

思路：

本题思路，是遇到一个没有遍历过的陆地，计数器就加一，然后把该节点所能遍历到的陆地都标记上。

在遇到标记过的陆地节点或海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

import java.util.*;public class Main {// 四个方向：右、下、左，上private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 四个方向都遍历一遍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;}// 如果未访问且是陆地(1)，则继续DFSif (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;dfs(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];// 计数器int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 发现未访问的陆地，岛屿数量加1，并开始DFS标记所有相连的陆地if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;count++;dfs(grid, visited, i, j);}}}System.out.println(count);in.close();}
}

遍历顺序：

DFS访问顺序:1  2  0  0  0 4  3  0  0  0 0  0  5  0  0 0  0  0  6  7 

方法：广搜

思路：

只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

import java.util.*;public class Main {// 四个方向：右、下、左，上private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 广搜private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Deque<int[]> que = new ArrayDeque<>();// 存储节点坐标que.offer(new int[] {x, y});// 加入队列后立即标记为已访问visited[x][y] = true;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 (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {que.offer(new int[] {nextX, nextY});visited[nextX][nextY] = true;}}}}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 count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 发现未访问的陆地，岛屿数量加1，并开始BFS标记所有相连的陆地if (!visited[i][j] && grid[i][j] == 1) {count++;bfs(grid, visited, i, j);}}}System.out.println(count);in.close();}
}

遍历顺序：

DFS访问顺序:1  2  0  0  0 4  3  0  0  0 0  0  5  0  0 0  0  0  6  7 
BFS访问顺序:1  2  0  0  0 3  4  0  0  0 0  0  5  0  0 0  0  0  6  7 

方法：深搜

思路：

在dfs递归的时候统计，每一层递归向上返回本次遍历到的岛屿数。

主函数里的循环，每次都是遇到一个新的岛屿，所以在主函数里，dfs回来之后，刷新maxLand。

import java.util.*;public class Main {// 四个方向：右、下、左，上private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private static int dfs(int[][] grid, boolean[][] visited, int x, int y) {// 坐标为x,y的本节点int sum = 1;// 四个方向都遍历一遍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;}// 如果未访问且是陆地(1)，则继续DFSif (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;// 加上从这个节点出发，深搜到的所有节点sum += dfs(grid, visited, nextX, nextY);}}// 返回给上一层return sum;}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 maxLand = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 发现未访问的陆地，岛屿数量加1，并开始DFS标记所有相连的陆地if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;// 每次从这里进去的，是一整个岛屿int land = dfs(grid, visited, i, j);// 刷新最大岛屿面积maxLand = Math.max(maxLand, land);}}}System.out.println(maxLand);in.close();}
}

方法：深搜

思路：

全局变量maxLand和count。

主函数里的循环，每次都是遇到一个新的岛屿，所以在主函数里，dfs之前，重置count=0，dfs回来之后，刷新maxLand。

import java.util.*;public class Main {// 四个方向：右、下、左，上private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private static int maxLand = 0;private static int count = 0;private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {count++;// 四个方向都遍历一遍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;}// 如果未访问且是陆地(1)，则继续DFSif (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;dfs(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++) {// 发现未访问的陆地，岛屿数量加1，并开始DFS标记所有相连的陆地if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;count = 0;dfs(grid, visited, i, j);maxLand = Math.max(res, count);}}}System.out.println(maxLand);in.close();}
}

方法：广搜

思路：

同上，接着用全局变量的方法，使用maxLand和count计数。

当队列que出队的时候，count++；

当回到主函数的时候，刷新maxLand。

import java.util.*;public class Main {// 四个方向：右、下、左，上private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private static int maxLand = 0;private static int count = 0;// 广搜private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Deque<int[]> que = new ArrayDeque<>();// 存储节点坐标que.offer(new int[] {x, y});// 加入队列后立即标记为已访问visited[x][y] = true;while (!que.isEmpty()) {// 每次弹出队列的时候，节点+1，岛屿面积++count++;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 (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {que.offer(new int[] {nextX, nextY});visited[nextX][nextY] = true;}}}}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++) {// 发现未访问的陆地，岛屿数量加1，并开始BFS标记所有相连的陆地if (!visited[i][j] && grid[i][j] == 1) {count = 0;bfs(grid, visited, i, j);maxLand = Math.max(maxLand, count);}}}System.out.println(maxLand);in.close();}
}