Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000Answer: 1
Example 2:
11000
11000
00100
00011Answer: 3
深度優(yōu)先搜索，要求的結(jié)果就是圖中連通份量的個(gè)數(shù)。更詳細(xì)的思路可以參考Find the number of islands。
//Runtime:13ms
class Solution {
public:
int numIslands(vector<vector<char>> &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int row = grid.size();
int col = grid[0].size();
int cnt = 0;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (grid[i][j] == '1')
{
cnt++;
dfs(grid, i, j);
}
}
}
return cnt;
}
private:
void dfs(vector<vector<char>> &grid, int row, int col)
{
if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != '1')
{
return;
}
grid[row][col] = 'X';
dfs(grid, row, col + 1);
dfs(grid, row + 1, col);
dfs(grid, row, col - 1);
dfs(grid, row - 1, col);
}
};
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
