200. Number of Islands
題目: 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
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
分析: 這道題可以用深度優(yōu)先搜索解決, 如果當前位置為1, 則置當前位置為'0'(已訪問), 并以當前位置中心遞歸的遍歷當前位置的上, 下, 左, 右四個位置. 直到grid中所有位置均為0. 代碼如下:
code:
class Solution {
public:
int numIslands(vector<vector<char> >& grid) {
if(grid.empty()) return 0;
int num = 0;
int row = grid.size();
int col = grid[0].size();
for (int i = 0; i < row; ++i){
for (int j = 0; j < col; ++j) {
if (grid[i][j] == '1') {
helper(i, j, grid);
num++;
}
}
}
return num;
}
void helper(int row, int col, vector<vector<char>>& grid) {
grid[row][col] = '0';
if (row-1>=0 && grid[row-1][col]=='1') {
helper(row-1, col, grid);
}
if (row+1<grid.size() && grid[row+1][col]=='1') {
helper(row+1, col, grid);
}
if (col-1>=0 && grid[row][col-1]=='1') {
helper(row, col-1, grid);
}
if (col+1<grid[0].size() && grid[row][col+1]=='1') {
helper(row, col+1, grid);
}
}
};
