題目

Lake counting

簡單翻譯一下，一塊被劃分為N*M小塊的田地，因?yàn)檫B續(xù)降雨導(dǎo)致部分小塊出現(xiàn)積水，有積水的小塊用“W”標(biāo)記，沒有積水的小塊用“.”標(biāo)記。一個小塊與周圍的8個小塊都屬于相鄰狀態(tài)，連續(xù)相鄰積水的小塊組成一個池塘。問給出的標(biāo)記后的田地一共有多少池塘？
上圖中的田地，一共有3塊池塘，左上角相鄰的“W”組成一塊，左下角相鄰的“W”組成一塊，右邊的一條“W”組成一塊。

解析

上面的二維數(shù)組表示的是一個圖結(jié)構(gòu)。我們從某一個“W”節(jié)點(diǎn)開始進(jìn)行深度遍歷，如果遇到“.”跳過，如果遇到“W”，改為“.”后（防止之后再一次的遍歷，保證只遍歷一次），繼續(xù)對這個點(diǎn)進(jìn)行深度遍歷，這樣得到的結(jié)果就是從起始的“W”節(jié)點(diǎn)開始，深度遍歷周圍的全部“W”節(jié)點(diǎn)，這些節(jié)點(diǎn)被包圍的“.”節(jié)點(diǎn)阻斷，此時就是一個池塘。接下來尋找下一個“W”節(jié)點(diǎn)，由于上一個“W”節(jié)點(diǎn)相鄰的“W”節(jié)點(diǎn)都被置成“.”節(jié)點(diǎn)，所以這一個“W”節(jié)點(diǎn)一定屬于另外的一個池塘。重復(fù)著上面的步驟，就可以找到所有的池塘，統(tǒng)計個數(shù)。

代碼

public class LakeCounting {
    //行數(shù)
    private int N;
    //列數(shù)
    private int M;

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

    //深度遍歷
    public void DFS(String[][] field, int i, int j){
        //如果訪問數(shù)據(jù)越界，直接返回
        if (i < 0 || j < 0){
            return;
        }
        if (i >= N || j >= M){
            return;
        }
        //如果節(jié)點(diǎn)為“.”，跳過
        if (field[i][j].equals(".")){
            return;
        }
        //如果節(jié)點(diǎn)為“W”
        if (field[i][j].equals("W")){
            //置為“.”
            field[i][j] = ".";
            //遞歸深度遍歷8個相鄰的節(jié)點(diǎn)
            //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","."}};
        //遍歷圖的二維數(shù)組
        for (int i = 0; i < 10; i++){
            for (int j = 0; j < 12; j++){
                //如果是“W”節(jié)點(diǎn)，進(jìn)行深度遍歷
                if (field[i][j].equals("W")){
                    //池塘數(shù)+1
                    count++;
                    //遞歸的深度遍歷，
                    //會把與當(dāng)前“W”節(jié)點(diǎn)相鄰和拓展后相鄰的所有“W”節(jié)點(diǎn)都訪問到
                    //組成一個池塘
                    counting.DFS(field, i, j);
                }
            }
        }
        System.out.println("count = " + count);
    }
}