題目來源
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
我印象中好像做過這道題沽讹，或者至少是類似的題目。最native的想法就是新建一個label數(shù)組武鲁，初始值為false爽雄。遍歷到1并且label為false的話就把1周圍的1用廣度優(yōu)先搜索搜到，label設(shè)為true沐鼠，把數(shù)目加1挚瘟，然后繼續(xù)遍歷。
再想了想發(fā)現(xiàn)不用設(shè)置label數(shù)組饲梭，直接把遍歷到的1變?yōu)?就可以了乘盖。
復(fù)雜度應(yīng)該是O(n^2)。然后可以AC憔涉，代碼如下：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (m == 0)
return 0;
int n = grid[0].size();
int res = 0;
for (int i=0; i<m; i++)
for (int j=0; j<n; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
res++;
}
}
return res;
}
void bfs(vector<vector<char>>& grid, int i, int j)
{
grid[i][j] = 0;
if (i-1>=0 && grid[i-1][j] == '1')
bfs(grid, i-1, j);
if (i+1<grid.size() && grid[i+1][j] == '1')
bfs(grid, i+1, j);
if (j-1>=0 && grid[i][j-1] == '1')
bfs(grid, i, j-1);
if (j+1<grid[0].size() && grid[i][j+1] == '1')
bfs(grid, i, j+1);
}
};
