当前位置：首页 > news >正文

Day 56 || 99.岛屿数量、100.岛屿的最大面积

news 2024/11/9 5:55:00

99.岛屿数量

题目链接：卡码网题目链接（ACM模式）

思路：深度搜索遍历整个二维数组当找到岛屿后，标记这个岛屿，岛屿总数量加一然后遍历这个点位的上下左右有没有1，然后递归这些1并标记，直到都是0为止，然后继续遍历二维数组跳已经遍历的熬的岛屿。

import java.util.Scanner;
public class Main{int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};public static void main (String[] args) {Main main = new Main();Scanner scanner = new Scanner(System.in);int x = scanner.nextInt();int y= scanner.nextInt();int[][] grid = new int[x][y];for(int i=0;i<x;i++){for(int j=0;j<y;j++){grid[i][j] = scanner.nextInt();} }int res = 0;for(int i=0;i<x;i++){for(int j=0;j<y;j++){if(grid[i][j]==1){grid[i][j] = 2;res++;main.die(grid,i,j); }}}System.out.println(res);       }public void die(int[][] grid,int x ,int y){for (int p = 0; p < 4; p++) { // 遍历当前节点的四个方向int nextx = x + dir[p][0];int nexty = y + dir[p][1]; // 获取周围四个方向的坐标// 检查边界条件if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {continue; // 坐标越界，跳过}// 如果节点未被访问过if (grid[nextx][nexty] == 1) {grid[nextx][nexty]=2;die(grid,nextx,nexty);}}}
}

广度搜索类似遍历二维数组，只不过是遇到1之后标记这个点，然后表用方法这个方法是使用搞一个队列来讲这个一周围的1都标记好变成一个小岛。

import java.util.Scanner;
import java.util.Stack;
import java.util.Map;
import java.util.AbstractMap;
public class Main{int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};public static void main (String[] args) {Main main = new Main();Scanner scanner = new Scanner(System.in);int x = scanner.nextInt();int y= scanner.nextInt();int[][] grid = new int[x][y];for(int i=0;i<x;i++){for(int j=0;j<y;j++){grid[i][j] = scanner.nextInt();} }int res = 0;for(int i=0;i<x;i++){for(int j=0;j<y;j++){if(grid[i][j]==1){grid[i][j]=2;res++;main.die(grid,i ,j);}} }System.out.println(res);       }public void die(int[][] grid,int startX ,int startY){Stack<Map.Entry<Integer, Integer>> stack = new Stack<>();stack.push(new AbstractMap.SimpleEntry<>(startX, startY));while(!stack.isEmpty()){Map.Entry<Integer, Integer> entry = stack.pop();int x = entry.getKey();int y = entry.getValue();for (int p = 0; p < 4; p++) { // 遍历当前节点的四个方向int nextx = x + dir[p][0];int nexty = y + dir[p][1]; // 获取周围四个方向的坐标// 检查边界条件if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {continue; // 坐标越界，跳过}// 如果节点未被访问过if (grid[nextx][nexty] == 1) {grid[nextx][nexty]=2;stack.push(new AbstractMap.SimpleEntry<>(nextx , nexty));}}}}
}