代码随想录算法训练营第51天|卡码网99. 岛屿数量、100. 岛屿的最大面积

1.卡码网99. 岛屿数量

题目链接：https://kamacoder.com/problempage.php?pid=1171
文章链接：https://www.programmercarl.com/kamacoder/0099.岛屿的数量深搜.html#_99-岛屿数量

本题思路:
遇到一个没有遍历过的节点陆地，计数器就加一，然后使用dfs或者bfs把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的节点或遇到海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

dfs的写法:

import java.util.*;public class Main{static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};// 四个方向public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 行int m = sc.nextInt(); // 列int[][] matrix = new int[n][m];for (int i = 0;i < n;i++) {for (int j = 0;j < m;j++) {matrix[i][j] = sc.nextInt();}}boolean[][] visted = new boolean[n][m];// 是否被访问过int res=0;for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 检查是否是未被标记的陆地if (!visted[i][j] && matrix[i][j] == 1) {// 未被标记过且是陆地res++;dfs(matrix,visted,i,j);// 将当前岛屿上的所有陆地都标记}}}System.out.println(res);}public static void dfs(int[][] matrix,boolean[][] visted,int x,int y) {if (visted[x][y] || matrix[x][y] == 0) { // 被访问过或者海洋 直接返回return;}visted[x][y] = true;for (int i=0;i<4;i++) {// 新坐标int ptx = x + dir[i][0];int pty = y + dir[i][1];// 检查坐标是否越界if (ptx<0 || ptx >= matrix.length || pty<0 || pty >= matrix[0].length) {continue;}dfs(matrix,visted,ptx,pty);}}}

bfs的写法：
注意：只要加入队列，立即标记该节点被访问过。

import java.util.*;public class Main{static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};// 四个方向public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 行int m = sc.nextInt(); // 列int[][] matrix = new int[n][m];for (int i = 0;i < n;i++) {for (int j = 0;j < m;j++) {matrix[i][j] = sc.nextInt();}}boolean[][] visted = new boolean[n][m];// 是否被访问过int res=0;for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 检查是否是未被标记的陆地if (!visted[i][j] && matrix[i][j] == 1) {res++;//        dfs(matrix,visted,i,j);// 将当前岛屿上的所有陆地都标记bfs(matrix,visted,i,j);}}}System.out.println(res);}//bfs写法public static void bfs(int[][] matrix,boolean[][] visted,int x,int y) {Deque<int[]> deque = new ArrayDeque<>();deque.offer(new int[]{x,y});visted[x][y] = true;//只要加入队列，立即标记该节点走过。while (!deque.isEmpty()) {int[] xy = deque.peek();int ptx = xy[0];int pty = xy[1];deque.poll();// 出队列for (int i=0;i<4;i++) {int nextx = ptx + dir[i][0];int nexty = pty + dir[i][1];//检查是否越界if (nextx<0 || nextx>=matrix.length || nexty<0 || nexty>=matrix[0].length) {continue;} //检查是否是未被标记的陆地if (!visted[nextx][nexty] && matrix[nextx][nexty]==1) {deque.offer(new int[]{nextx,nexty});visted[nextx][nexty] = true;// 只要加入队列，立即标记该节点走过。}}}}
}

以上使用dfs或者bfs的目的都是：把该岛屿所能遍历到的陆地都标记上，不会统计到其他岛屿上。

2.卡码网100. 岛屿的最大面积

题目链接：https://kamacoder.com/problempage.php?pid=1172
文章链接：https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html#思路

思路：与岛屿数量一致。只是统计的是面积。
dfs版本：

import java.util.*;public class Main {static int max = 0;static int area = 0;static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();//行int M = sc.nextInt();//列int[][] matrix = new int[N][M];boolean[][] visted = new boolean[N][M];for (int i=0;i<N;i++) {for (int j=0;j<M;j++) {matrix[i][j] = sc.nextInt();}}for (int i=0;i<N;i++) {for (int j=0;j<M;j++) {// 检查是否是未被标记的陆地if (!visted[i][j] && matrix[i][j] == 1) {//标记该岛屿所有陆地并统计面积dfs(matrix,visted,i,j);//bfs(matrix,visted,i,j);max = Math.max(area,max);area=0;}}}System.out.println(max);}//dfspublic static void dfs(int[][] matrix,boolean[][] visted,int x,int y) {// 检查是否是被标记或者海洋if (visted[x][y] || matrix[x][y] == 0) {return;}visted[x][y] = true;area++;//面积加一for (int i=0;i<4;i++) {int ptx = x + dir[i][0];int pty = y + dir[i][1];// 检查是否越界if (ptx<0||ptx>=matrix.length||pty<0||pty>=matrix[0].length) {continue;}dfs(matrix,visted,ptx,pty);}}
}

bfs版本：

import java.util.*;public class Main {static int max = 0;static int area = 0;static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();//行int M = sc.nextInt();//列int[][] matrix = new int[N][M];boolean[][] visted = new boolean[N][M];for (int i=0;i<N;i++) {for (int j=0;j<M;j++) {matrix[i][j] = sc.nextInt();}}for (int i=0;i<N;i++) {for (int j=0;j<M;j++) {// 检查是否是未被标记的陆地if (!visted[i][j] && matrix[i][j] == 1) {//标记该岛屿所有陆地并统计面积//dfs(matrix,visted,i,j);bfs(matrix,visted,i,j);max = Math.max(area,max);area=0;}}}System.out.println(max);}//bfspublic static void bfs(int[][] matrix,boolean[][] visted,int x,int y) {Deque<int[]> queue = new ArrayDeque<>();queue.offer(new int[]{x,y});visted[x][y]=true;area++;//面积加一while (!queue.isEmpty()) {int ptx = (queue.peek())[0];int pty = (queue.peek())[1];queue.poll();//出队列for (int i=0;i<4;i++) {int nextx = ptx + dir[i][0];int nexty = pty + dir[i][1];// 检查是否越界if (nextx<0 || nextx>=matrix.length ||nexty<0||nexty>=matrix[0].length) {continue;}// 检查是否是未被标记的陆地if (!visted[nextx][nexty]&&matrix[nextx][nexty]==1) {queue.offer(new int[]{nextx,nexty});visted[nextx][nexty] = true;area++;//面积加一}}}}
}