题目链接：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

这道题的要求是计算有多少岛。其中，在只包含0和1二维平面上，0表示水，1表示岛，并且只有垂直和水平方向算是连接的。

实则统计有几组相互连接的1。可以利用深度优先搜索或者广度优先搜索，把相互连接的1都改为0。接着只要再用个计数器即可。

  1. DFS

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        
        int res = 0;
        for(int i = 0; i < grid.size(); ++ i)
            for(int j = 0; j < grid[0].size(); ++ j)
                if(grid[i][j] == '1')
                {
                    ++ res;
                    DFS(grid, i, j);
                }
        return res;
    }
private:
    void DFS(vector<vector<char>> &grid, int x, int y)
    {
        grid[x][y] = '0';
        if(x > 0 && grid[x - 1][y] == '1')
            DFS(grid, x - 1, y);
        if(x < grid.size() - 1 && grid[x + 1][y] == '1')
            DFS(grid, x + 1, y);
        if(y > 0 && grid[x][y - 1] == '1')
            DFS(grid, x, y - 1);
        if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
            DFS(grid, x, y + 1);
    }
};

  1. BFSB

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        
        int res = 0;
        for(int i = 0; i < grid.size(); ++ i)
            for(int j = 0; j < grid[0].size(); ++ j)
                if(grid[i][j] == '1')
                {
                    ++ res;
                    BFS(grid, i, j);
                }
        return res;
    }
private:
    void BFS(vector<vector<char>> &grid, int x, int y)
    {
        queue<vector<int>> q;
        q.push({x, y});
        grid[x][y] = '0';
        
        while(!q.empty())
        {
            x = q.front()[0], y = q.front()[1];
            q.pop();
            
            if(x > 0 && grid[x - 1][y] == '1')
            {
                q.push({x - 1, y});
                grid[x - 1][y] = '0';
            }
            if(x < grid.size() - 1 && grid[x + 1][y] == '1')
            {
                q.push({x + 1, y});
                grid[x + 1][y] = '0';
            }
            if(y > 0 && grid[x][y - 1] == '1')
            {
                q.push({x, y - 1});
                grid[x][y - 1] = '0';
            }
            if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
            {
                q.push({x, y + 1});
                grid[x][y + 1] = '0';
            }
        }
    }
};