信息学奥赛一本通T1249- Lake Counting (BFS,DFS) java 题解

解题思路:

               遇到一个水洼(W)进行扩散标记为干燥(.) 计数加一(count++)

               依次遍历去除       

参考代码:

 BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 水洼_BFS {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        char[][] arr = new char[n][m];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLine().toCharArray();
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //依次找到每一个水洼
                if (arr[i][j] == 'W') {
                    //BFS扩散
                    BFS(arr, i, j);
                    //记录水洼数
                    count++;
                }
            }
        }
        System.out.println(count);

    }
    //扩散方向 上右下左，左上，右上，左下，右下 八个方向
    static int[][] direction = {{0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}, {-1, 0}, {0, -1}};

    private static void BFS(char[][] arr, int startx, int starty) {
        LinkedList<course> queue = new LinkedList<course>();
        queue.add(new course(startx, starty));//入队
        while (!queue.isEmpty()) {
            course c = queue.poll();//去除队列中第一个水洼
            arr[c.x][c.y] = '.';//去除水洼
            for (int k = 0; k < 8; k++) {
                int x = c.x + direction[k][0];
                int y = c.y + direction[k][1];
                //边界校验
                if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && arr[x][y] == 'W') {
                    queue.addLast(new course(x,y));//添加一下个水洼
                }
            }
        }

    }

}

class course {
    public int x;//行号
    public int y;//列号

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

 DFS

import java.util.Scanner;

public class 水洼_DFS {
    //水洼
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        char[][] arr = new char[n][m];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLine().toCharArray();
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //依次找到每一个水洼
                if (arr[i][j] == 'W') {
                    //DFS扩散
                    dfs(i, j, arr);
                    //记录水洼数
                    count++;
                }
            }
        }
        System.out.println(count);


    }

    //扩散方向 上右下左，左上，右上，左下，右下 八个方向
    static int[][] direction = {{0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}, {-1, 0}, {0, -1}};

    private static void dfs(int i, int j, char[][] arr) {
        arr[i][j] = '.';//去除水洼
        for (int k = 0; k < 8; k++) {
            int x = i + direction[k][0];
            int y = j + direction[k][1];
            //边界校验
            if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && arr[x][y] == 'W') {
                dfs(x, y, arr);
            }
        }
    }


}