java如何使用BFS和DFS兩種方式解島嶼數(shù)量

這篇文章主要為大家展示了java如何使用BFS和DFS兩種方式解島嶼數(shù)量，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶大家一起來研究并學(xué)習(xí)一下“java如何使用BFS和DFS兩種方式解島嶼數(shù)量”這篇文章吧。

However dark and scary the world might be right now, there will be light.

無論世界現(xiàn)在有多黑暗，多可怕，終有一天會重現(xiàn)光明。

問題描述

給你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 1:

輸入:

[

['1','1','1','1','0'],

['1','1','0','1','0'],

['1','1','0','0','0'],

['0','0','0','0','0']

]

輸出: 1

示例 2:

輸入:

[

['1','1','0','0','0'],

['1','1','0','0','0'],

['0','0','1','0','0'],

['0','0','0','1','1']

]

輸出: 3

解釋: 每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成。

DFS解決

這題讓求的是島嶼的面積，二維數(shù)組中值是1的都是島嶼，如果多個1是連著的，那么他們只能算一個島嶼。

最簡單的一種方式就是遍歷數(shù)組中的每一個值，如果是1就說明是島嶼，然后把它置為0或者其他的字符都可以，只要不是1就行，然后再遍歷他的上下左右4個位置。如果是1，說明這兩個島嶼是連著的，只能算是一個島嶼，我們還要把它置為0，然后再以它為中心遍歷他的上下左右4個位置……。如果是0，就說明不是島嶼，就不在往他的上下左右4個位置遍歷了。這里就以示例1為例來看一下

每個位置只要是1，先要把它置為0，然后沿著他的上下左右4個方向繼續(xù)遍歷，執(zhí)行同樣的操作，要注意邊界條件的判斷。代碼比較簡單，來看下

 1public int numIslands(char[][] grid) { 2    //邊界條件判斷 3    if (grid == null || grid.length == 0) 4        return 0; 5    //統(tǒng)計島嶼的個數(shù) 6    int count = 0; 7    //兩個for循環(huán)遍歷每一個格子 8    for (int i = 0; i < grid.length; i++) 9        for (int j = 0; j < grid[0].length; j++) {10            //只有當前格子是1才開始計算11            if (grid[i][j] == '1') {12                //如果當前格子是1，島嶼的數(shù)量加113                count++;14                //然后通過dfs把當前格子的上下左右415                //個位置為1的都要置為0，因為他們是連著16                //一起的算一個島嶼，17                dfs(grid, i, j);18            }19        }20    //最后返回島嶼的數(shù)量21    return count;22}2324//這個方法會把當前格子以及他鄰近的為1的格子都會置為125public void dfs(char[][] grid, int i, int j) {26    //邊界條件判斷，不能越界27    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')28        return;29    //把當前格子置為0，然后再從他的上下左右4個方向繼續(xù)遍歷30    grid[i][j] = '0';31    dfs(grid, i - 1, j);//上32    dfs(grid, i + 1, j);//下33    dfs(grid, i, j + 1);//左34    dfs(grid, i, j - 1);//右35}

BFS解決

DFS就是沿著一條路徑一直走下去，當遇到終止條件的時候才會返回，而BFS就是先把當前位置附近的訪問一遍，就像下面這樣先訪問圈內(nèi)的，然后再把圈放大繼續(xù)訪問，就像下面這樣

這題使用BFS和DFS都能解決，如果遇到位置為1的格子，只要能把他們挨著的為1的全部置為0，然后挨著的挨著的為1的位置也置為0，然后……一直這樣循環(huán)下去，看下代碼

 1public int numIslands(char[][] grid) { 2    //邊界條件判斷 3    if (grid == null || grid.length == 0) 4        return 0; 5    //統(tǒng)計島嶼的個數(shù) 6    int count = 0; 7    //兩個for循環(huán)遍歷每一個格子 8    for (int i = 0; i < grid.length; i++) 9        for (int j = 0; j < grid[0].length; j++) {10            //只有當前格子是1才開始計算11            if (grid[i][j] == '1') {12                //如果當前格子是1，島嶼的數(shù)量加113                count++;14                //然后通過bfs把當前格子的上下左右415                //個位置為1的都要置為0，因為他們是連著16                //一起的算一個島嶼，17                bfs(grid, i, j);18            }19        }20    return count;21}2223private void bfs(char[][] grid, int x, int y) {24    //把當前格子先置為025    grid[x][y] = '0';26    int n = grid.length;27    int m = grid[0].length;28    //使用隊列，存儲的是格子坐標轉(zhuǎn)化的值29    Queue<Integer> queue = new LinkedList<>();30    //我們知道平面坐標是兩位數(shù)字，但隊列中存儲的是一位數(shù)字，31    //所以這里是把兩位數(shù)字轉(zhuǎn)化為一位數(shù)字32    int code = x * m + y;33    //坐標轉(zhuǎn)化的值存放到隊列中34    queue.add(code);35    while (!queue.isEmpty()) {36        //出隊37        code = queue.poll();38        //在反轉(zhuǎn)成坐標值（i，j）39        int i = code / m;40        int j = code % m;41        if (i > 0 && grid[i - 1][j] == '1') {//上42            //如果上邊格子為1，把它置為0，然后加入到隊列中43            //下面同理44            grid[i - 1][j] = '0';45            queue.add((i - 1) * m + j);46        }47        if (i < n - 1 && grid[i + 1][j] == '1') {//下48            grid[i + 1][j] = '0';49            queue.add((i + 1) * m + j);50        }51        if (j > 0 && grid[i][j - 1] == '1') { //左52            grid[i][j - 1] = '0';53            queue.add(i * m + j - 1);54        }55        if (j < m - 1 && grid[i][j + 1] == '1') {//右56            grid[i][j + 1] = '0';57            queue.add(i * m + j + 1);58        }59    }60}

Java的特點有哪些

Java的特點有哪些 1.Java語言作為靜態(tài)面向?qū)ο缶幊陶Z言的代表，實現(xiàn)了面向?qū)ο罄碚?，允許程序員以優(yōu)雅的思維方式進行復(fù)雜的編程。 2.Java具有簡單性、面向?qū)ο?、分布式、安全性、平臺獨立與可移植性、動態(tài)性等特點。 3.使用Java可以編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等。

以上就是關(guān)于“java如何使用BFS和DFS兩種方式解島嶼數(shù)量”的內(nèi)容，如果該文章對你有所幫助并覺得寫得不錯，勞請分享給你的好友一起學(xué)習(xí)新知識，若想了解更多相關(guān)知識內(nèi)容，請多多關(guān)注億速云行業(yè)資訊頻道。