[Vssue]kamacoder/0099.岛屿的数量深搜.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E6%B7%B1%E6%90%9C.html

[lkh2022]

java版本： import java.util.Scanner;

public class Main{ static int[][] directions = {{-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[][] grid = new int[n][m];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            grid[i][j] = sc.nextInt();
        }
    }
    boolean[][] visited = new boolean[n][m];
    int res = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j] && grid[i][j] == 1){
                res++;
                dfs(grid, visited, i, j);
            }
        }
    }

    System.out.println(res);
}

private static void dfs(int[][] grid, boolean[][] visited, int x, int y){
    if (visited[x][y] || grid[x][y] == 0) return;
    visited[x][y] = true;
    for(int[] dir : directions){
        int newX = x + dir[0];
        int newY = y + dir[1];
        if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length){
            continue;
        }
        dfs(grid, visited,newX,newY);
    }

}

}

[1132178599]

java版本： import java.util.Scanner; public class Main{ static int[][]dir={{-1,0},{1,0},{0,-1},{0,1}}; public static void dps(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; } if(visited[nextx][nexty]==false&&grid[nextx][nexty]==1) { visited[nextx][nexty]=true; dps(grid,visited,nextx,nexty); } } } public static void main (String[] args) { Scanner s=new Scanner(System.in); int n=s.nextInt(); int m=s.nextInt(); int [][]grid=new int[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { grid[i][j]=s.nextInt(); } } boolean[][]visited=new boolean[n][m]; int result = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (visited[i][j]==false && grid[i][j] == 1) { visited[i][j] = true; result++; dps(grid, visited, i, j); // 将与其链接的陆地都标记上 true } } } System.out.println(result); } }