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

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

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

示例 1:

輸入:
11110
11010
11000
00000
輸出:?1
示例?2:

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

?思路：這道題類似于圖像處理領(lǐng)域找二值圖像四鄰域連通數(shù)，體現(xiàn)的是廣度優(yōu)先的思想，具體的，遍歷每個(gè)數(shù)，如果當(dāng)前數(shù)為1，那么以此展開去找上下左右為1的值，并把這些搜索到的值都變?yōu)?，這樣遍歷的時(shí)候就不再遍歷這些點(diǎn)，因?yàn)檫@些點(diǎn)已經(jīng)屬于某一個(gè)島嶼了，BFS注意返回條件。

?

class Solution { public:int numIslands(vector<vector<char>>& grid) {if(grid.empty())return 0;int rows = grid.size();int cols = grid[0].size();int counts = 0;for(int i=0;i<rows;++i){for(int j=0;j<cols;++j){if(grid[i][j]=='1'){BFS(grid,i,j,rows,cols);counts++;} }}return counts;}void BFS(vector<vector<char>>& grid,int i,int j,int rows,int cols){if(i<0 || i>=rows || j<0 || j>=cols || \grid[i][j]=='0')return;grid[i][j] = '0';BFS(grid,i-1,j,rows,cols);BFS(grid,i+1,j,rows,cols);BFS(grid,i,j-1,rows,cols);BFS(grid,i,j+1,rows,cols);} };

?

總結(jié)

以上是生活随笔為你收集整理的岛屿数量—leetcode200的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。