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:
Input: 11110 11010 11000 00000 Output: 1
Example 2:
Input: 11000 11000 00100 00011 Output: 3
给定一个二维数组，标’1’表示陆地，标’0’表示水。问这个网格中共有多少个岛屿。一个岛屿就是若干个联通的’1’。 简单题，对所有标’1’的网格进行DFS或BFS，把所有联通的’1’都标记一下。下次遇到一个没标记的’1’就代表一个新的岛屿的出现。 完整代码如下：
class Solution {
private:
void dfs(vector<vector<char> >& grid, vector<vector<int> >& mark, int i, int j, const int& m, const int& n)
{
mark[i][j] = 1;
if (i – 1 >= 0 && grid[i – 1][j] == ‘1’ && mark[i – 1][j] == 0)
dfs(grid, mark, i – 1, j, m, n);
if (i + 1 < m && grid[i + 1][j] == ‘1’ && mark[i + 1][j] == 0)
dfs(grid, mark, i + 1, j, m, n);
if (j – 1 >= 0 && grid[i][j – 1] == ‘1’ && mark[i][j – 1] == 0)
dfs(grid, mark, i, j – 1, m, n);
if (j + 1 < n && grid[i][j + 1] == ‘1’ && mark[i][j + 1] == 0)
dfs(grid, mark, i, j + 1, m, n);
}
public:
int numIslands(vector<vector<char> >& grid)
{
int m = grid.size(), n = 0;
if (m != 0)
n = grid[0].size();
if (m == 0 || n == 0)
return 0;
vector<vector<int> > mark(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == ‘1’ && mark[i][j] == 0) {
++ans;
dfs(grid, mark, i, j, m, n);
}
}
}
return ans;
}
};本代码提交AC，用时9MS。