youngyangyang04/leetcode-master-comment

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

Opened this issue · 2 comments

lkh2022 commented

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 commented

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);
}
}

  • 👍1
  • ❤️1