Day52 图论part03

101.孤岛的总面积

基础题目 可以自己尝试做一做 。

代码随想录

方法1：深度搜索

import java.util.*;

public class Main{
    public static int[][] dirc = {
   {0,1},{1,0},{0,-1},{-1,0}};
    
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] graph = new int[n][m];
        for(int i  = 0; i < n ; i++){
            for(int j = 0; j < m; j++){
                graph[i][j] = scanner.nextInt();
            }
        }
        
        boolean[][] visited = new boolean[n][m];
        
        for(int i = 0; i < n; i++){
            if(graph[i][0] == 1){
                dfs(graph, visited, i , 0);
            }
            if(graph[i][m-1] == 1){
                dfs(graph, visited, i , m-1);
            }
        }
        
        for(int j = 0; j < m; j++){
            if(graph[0][j] == 1){
                dfs(graph, visited, 0, j);
            }
            if(graph[n-1][j] == 1){
                dfs(graph, visited, n-1, j);
            }
        }
        
        int sum = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(graph[i][j] == 1){
                    sum ++;
                }
            }
        }
        
       System.out.println(sum);
    }
    
    public static void dfs(int[][] graph, boolean[][] visited, int x, int y){
        if(!(x >= 0 && x < graph.length && y >= 0 && y < graph[0].length )){
            return ;
        }
        if(visited[x][y] || graph[x][y] == 0){
            return ;
        }
        
        
        visited[x][y] = true;
        graph[x][y] = 0;
        for(int i = 0; i < dirc.length; i++){
            int nextX = x + dirc[i][0];
            int nextY = y + dirc[i][1];
            dfs(graph, visited, nextX, nextY);
        }
        
    }
    
}

方法2：广度搜索

import java.util.*;

public class Main{
    public static int[][] dirc = {
   {0,1},{1,0},{0,-1},{-1,0}};
    
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] graph = new int[n][m];
        for(int i  = 0; i < n ; i++){
            for(int j = 0; j < m; j++){
                graph[i][j] = scanner.nextInt();
            }
        }
        
        boolean[][] visited = new boolean[n][m];
        
        for(int i = 0; i < n; i++){
            if(graph[i][0] == 1){
                bfs(graph, visited, i , 0);
            }
            if(graph[i][m-1] == 1){
                bfs(graph, visited, i , m-1);
            }
        }
        
        for(int j = 0; j < m; j++){
            if(graph[0][j] == 1){
                bfs(graph, visited, 0, j);
            }
            if(graph[n-1][j] == 1){
                bfs(graph, visited, n-1, j);
            }
        }
        
        int sum = 0;
        for(int i = 0; i < n; i+&