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
我印象中好像做过这道题，或者至少是类似的题目。最native的想法就是新建一个label数组，初始值为false。遍历到1并且label为false的话就把1周围的1用广度优先搜索搜到，label设为true，把数目加1，然后继续遍历。
再想了想发现不用设置label数组，直接把遍历到的1变为0就可以了。
复杂度应该是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);
    }
};