题目描述

陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
也就是说如果连通块(岛屿)内的点(陆地)都临海，这个联通块(岛屿)就会被淹

bfs

import java.util.*;

public class Main {

    static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    //dx和dy代表偏移量数组 用来枚举上右下左四个方向
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    static int N = 1010;

    static int n;

    //total是岛屿的陆地数量  bound是岛屿内的临海的陆地数量
    static int total, bound;

    //存图
    static char[][] g = new char[N][N];
    //判断每个点有没有被搜过
    static boolean[][] st = new boolean[N][N];
    //最多N*N个点，也就是N*N个状态
    static Pair[] q = new Pair[N * N];


    static void bfs(int x, int y) {
        //hh为队首 tt为队尾
        int hh = 0, tt = 0;
        //放入状态表
        q[0] = new Pair(x, y);
        //当前点被搜过 被设为true
        st[x][y] = true;

        while (hh <= tt) {

            //取队首元素
            Pair t = q[hh++];

            //岛屿内的陆地+1(也就是连通块内的点数+1)
            total++;

            //判断当前的点是否临海
            boolean is_bound = false;

            for (int i = 0; i < 4; i++) {

                int a = t.x + dx[i];

                int b = t.y + dy[i];

                if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b]){
                    if(g[a][b] == '.') {
                      is_bound = true;//当前点临海 
                      continue;
                    }else {
                      //把元素放入队尾
                      q[++tt] = new Pair(a, b);
                      //该点被扫过，设为true
                      st[a][b] = true;
                    }
                }

            }

            if (is_bound) bound++; //当前点临海！ 
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int res = 0;

        //当你使用 nextInt()等方法读取基本类型时，输入缓冲区中的换行符可能会留在缓冲区中，
        //如果不消耗这个换行符，后续的 nextLine() 将会读取到一个空行。
        //因此，在读取完整数后，调用scanner.nextLine().
        //可以确保输入缓冲区中的换行符被消耗掉，以便后续的 nextLine() 可以正常读取下一行的输入。
        scanner.nextLine();


        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                g[i][j] = line.charAt(j);
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //如果当前点为#，且这个点没被搜过
                if (g[i][j] == '#' && !st[i][j]) {

                    //total是岛屿的陆地数量  bound是岛屿内的临海的陆地数量
                    total = 0;
                    bound = 0;

                    //就搜一下这个点(也就是找这个点所在的联通块)
                    bfs(i, j);

                    //System.out.println(total +" "+ bound);

                    //如果岛屿的陆地数量 = 岛屿的临海的陆地数量
                    if (total == bound) {
                        //说明这个岛屿会被淹没
                        res++;
                    }
                }
            }
        }

        System.out.println(res);
    }
}

dfs

import java.util.*;

public class Main {

    //dx和dy代表偏移量数组 用来枚举上右下左四个方向
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    static int N = 1010;
    static int n;
    //存图
    static char[][] g = new char[N][N];
    //判断每个点有没有被搜过
    static boolean[][] st = new boolean[N][N];
    //total是岛屿的陆地数量  bound是岛屿内的临海的陆地数量
    static int total,bound;


    static void dfs(int x, int y) {

           //当前点被搜过 被设为true
           st[x][y] = true;

           //岛屿内的陆地+1(也就是连通块内的点数+1)
           total++;

           //判断当前的点是否临海
           boolean is_bound = false;

           for(int i = 0 ; i < 4 ; i++){

               int a = x + dx[i];

               int b = y + dy[i];

               //该点没越界，该点没被扫过
               if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b]){
                    if(g[a][b] == '.') {
                      is_bound = true;//当前点临海 
                      continue;
                    }else {
                      dfs(a, b);//继续扫这个点
                    }
                }
           }

           if (is_bound) bound++; //当前点临海！
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int res = 0;

        //当你使用 nextInt()等方法读取基本类型时，输入缓冲区中的换行符可能会留在缓冲区中，
        //如果不消耗这个换行符，后续的 nextLine() 将会读取到一个空行。
        //因此，在读取完整数后，调用scanner.nextLine().
        //可以确保输入缓冲区中的换行符被消耗掉，以便后续的 nextLine() 可以正常读取下一行的输入。
        scanner.nextLine();


        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                g[i][j] = line.charAt(j);
            }
        } 


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //如果当前点为#，且这个点没被搜过
                if (g[i][j] == '#' && !st[i][j]) {

                    //total是岛屿的陆地数量  bound是岛屿内的临海的陆地数量
                    total = 0; bound = 0;

                    //就搜一下这个点(也就是找这个点所在的联通块)
                    dfs(i, j);

                    //System.out.println(total +" "+ bound);

                    //如果岛屿的陆地数量 = 岛屿的临海的陆地数量
                    if(total == bound){
                        //说明这个岛屿会被淹没
                        res++;
                    }
                }
            }
        }

        System.out.println(res);
    }
}