Lake counting

题目

Lake counting

简单翻译一下，一块被划分为N*M小块的田地，因为连续降雨导致部分小块出现积水，有积水的小块用“W”标记，没有积水的小块用“.”标记。一个小块与周围的8个小块都属于相邻状态，连续相邻积水的小块组成一个池塘。问给出的标记后的田地一共有多少池塘？
上图中的田地，一共有3块池塘，左上角相邻的“W”组成一块，左下角相邻的“W”组成一块，右边的一条“W”组成一块。

解析

上面的二维数组表示的是一个图结构。我们从某一个“W”节点开始进行深度遍历，如果遇到“.”跳过，如果遇到“W”，改为“.”后（防止之后再一次的遍历，保证只遍历一次），继续对这个点进行深度遍历，这样得到的结果就是从起始的“W”节点开始，深度遍历周围的全部“W”节点，这些节点被包围的“.”节点阻断，此时就是一个池塘。接下来寻找下一个“W”节点，由于上一个“W”节点相邻的“W”节点都被置成“.”节点，所以这一个“W”节点一定属于另外的一个池塘。重复着上面的步骤，就可以找到所有的池塘，统计个数。

代码

public class LakeCounting {
    //行数
    private int N;
    //列数
    private int M;

    public LakeCounting(int n, int m) {
        N = n;
        M = m;
    }

    //深度遍历
    public void DFS(String[][] field, int i, int j){
        //如果访问数据越界，直接返回
        if (i < 0 || j < 0){
            return;
        }
        if (i >= N || j >= M){
            return;
        }
        //如果节点为“.”，跳过
        if (field[i][j].equals(".")){
            return;
        }
        //如果节点为“W”
        if (field[i][j].equals("W")){
            //置为“.”
            field[i][j] = ".";
            //递归深度遍历8个相邻的节点
            //upper left corner
            DFS(field, i - 1, j - 1);
            //upper
            DFS(field, i - 1, j);
            //upper right corner
            DFS(field, i - 1, j + 1);
            //left
            DFS(field, i, j -1);
            //right
            DFS(field, i, j + 1);
            //lower left corner
            DFS(field, i + 1, j -1);
            //lower
            DFS(field, i + 1, j);
            //lower right corner
            DFS(field, i + 1, j + 1);
        }
    }

    public static void main(String[] args){
        int count = 0;
        LakeCounting counting = new LakeCounting(10, 12);
        String[][] field = {
                {"W",".",".",".",".",".",".",".",".","W","W","."},
                {".","W","W","W",".",".",".",".",".","W","W","W"},
                {".",".",".",".","W","W",".",".",".","W","W","."},
                {".",".",".",".",".",".",".",".",".","W","W","."},
                {".",".",".",".",".",".",".",".",".","W",".","."},
                {".",".","W",".",".",".",".",".",".","W",".","."},
                {".","W",".","W",".",".",".",".",".","W","W","."},
                {"W",".","W",".","W",".",".",".",".",".","W","."},
                {".","W",".","W",".",".",".",".",".",".","W","."},
                {".",".","W",".",".",".",".",".",".",".","W","."}};
        //遍历图的二维数组
        for (int i = 0; i < 10; i++){
            for (int j = 0; j < 12; j++){
                //如果是“W”节点，进行深度遍历
                if (field[i][j].equals("W")){
                    //池塘数+1
                    count++;
                    //递归的深度遍历，
                    //会把与当前“W”节点相邻和拓展后相邻的所有“W”节点都访问到
                    //组成一个池塘
                    counting.DFS(field, i, j);
                }
            }
        }
        System.out.println("count = " + count);
    }
}