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

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

10多年的尚志網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。營(yíng)銷型網(wǎng)站建設(shè)的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整尚志建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)公司從事“尚志網(wǎng)站設(shè)計(jì)”,“尚志網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

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

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

問(wèn)題描述

給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(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的都是島嶼，如果多個(gè)1是連著的，那么他們只能算一個(gè)島嶼。

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

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

 1public int numIslands(char[][] grid) { 2    //邊界條件判斷 3    if (grid == null || grid.length == 0) 4        return 0; 5    //統(tǒng)計(jì)島嶼的個(gè)數(shù) 6    int count = 0; 7    //兩個(gè)for循環(huán)遍歷每一個(gè)格子 8    for (int i = 0; i < grid.length; i++) 9        for (int j = 0; j < grid[0].length; j++) {10            //只有當(dāng)前格子是1才開(kāi)始計(jì)算11            if (grid[i][j] == '1') {12                //如果當(dāng)前格子是1，島嶼的數(shù)量加113                count++;14                //然后通過(guò)dfs把當(dāng)前格子的上下左右415                //個(gè)位置為1的都要置為0，因?yàn)樗麄兪沁B著16                //一起的算一個(gè)島嶼，17                dfs(grid, i, j);18            }19        }20    //最后返回島嶼的數(shù)量21    return count;22}2324//這個(gè)方法會(huì)把當(dāng)前格子以及他鄰近的為1的格子都會(huì)置為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    //把當(dāng)前格子置為0，然后再?gòu)乃纳舷伦笥?個(gè)方向繼續(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就是沿著一條路徑一直走下去，當(dāng)遇到終止條件的時(shí)候才會(huì)返回，而B(niǎo)FS就是先把當(dāng)前位置附近的訪問(wèn)一遍，就像下面這樣先訪問(wèn)圈內(nèi)的，然后再把圈放大繼續(xù)訪問(wèn)，就像下面這樣

這題使用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)計(jì)島嶼的個(gè)數(shù) 6    int count = 0; 7    //兩個(gè)for循環(huán)遍歷每一個(gè)格子 8    for (int i = 0; i < grid.length; i++) 9        for (int j = 0; j < grid[0].length; j++) {10            //只有當(dāng)前格子是1才開(kāi)始計(jì)算11            if (grid[i][j] == '1') {12                //如果當(dāng)前格子是1，島嶼的數(shù)量加113                count++;14                //然后通過(guò)bfs把當(dāng)前格子的上下左右415                //個(gè)位置為1的都要置為0，因?yàn)樗麄兪沁B著16                //一起的算一個(gè)島嶼，17                bfs(grid, i, j);18            }19        }20    return count;21}2223private void bfs(char[][] grid, int x, int y) {24    //把當(dāng)前格子先置為025    grid[x][y] = '0';26    int n = grid.length;27    int m = grid[0].length;28    //使用隊(duì)列，存儲(chǔ)的是格子坐標(biāo)轉(zhuǎn)化的值29    Queue<Integer> queue = new LinkedList<>();30    //我們知道平面坐標(biāo)是兩位數(shù)字，但隊(duì)列中存儲(chǔ)的是一位數(shù)字，31    //所以這里是把兩位數(shù)字轉(zhuǎn)化為一位數(shù)字32    int code = x * m + y;33    //坐標(biāo)轉(zhuǎn)化的值存放到隊(duì)列中34    queue.add(code);35    while (!queue.isEmpty()) {36        //出隊(duì)37        code = queue.poll();38        //在反轉(zhuǎn)成坐標(biāo)值（i，j）39        int i = code / m;40        int j = code % m;41        if (i > 0 && grid[i - 1][j] == '1') {//上42            //如果上邊格子為1，把它置為0，然后加入到隊(duì)列中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的特點(diǎn)有哪些

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

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

新聞名稱：java如何使用BFS和DFS兩種方式解島嶼數(shù)量
文章起源：http://muchs.cn/article42/jepdhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開(kāi)發(fā)、商城網(wǎng)站、電子商務(wù)、移動(dòng)網(wǎng)站建設(shè)、域名注冊(cè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)