leetcode200.岛屿的个数

经典的dfs、bfs问题。

问题描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
  输入:
  11110
  11010
  11000
  00000
  输出: 1
示例 2:
  输入:
  11000
  11000
  00100
  00011
  输出: 3

思路

• 经典的 DFS | BFS 问题，搜索连通域的个数

Code: DFS

思路很简单，通过一个dfs找出连通的岛屿然后标志为0，如此以往直至没有1。

class Solution {
    int n, m;
public:
    int numIslands(vector<vector<char>>& grid) {  // 注意：是 char 不是 int
        if (!grid.empty()) n = grid.size();
        else return 0;
        if (!grid[0].empty()) m = grid[0].size();
        else return 0;
        
        int ret = 0;
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++) {
                if (grid[i][j] != '0') {
                    ret += 1;
                    dfs(grid, i, j);
                }
            }
        
        return ret;
    }
    
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= m )  // 边界判断（递归基）
            return;
            
        if (grid[i][j] == '0')
            return;
        else {
            grid[i][j] = '0';  // 如果不想修改原数据，可以复制一个
            // 4 个方向 dfs；一些问题会扩展成 8 个方向，本质上没有区别
            dfs(grid, i+1, j);
            dfs(grid, i-1, j);
            dfs(grid, i, j+1);
            dfs(grid, i, j-1);
        }
    }
};

Code: BFS

class Solution {
    int n, m;
public:
    int numIslands(vector<vector<char>>& grid) {
        if (!grid.empty()) n = grid.size();
        else return 0;
        if (!grid[0].empty()) m = grid[0].size();
        else return 0;
        
        int ret = 0;
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++) {
                if (grid[i][j] != '0') {
                    ret += 1;
                    bfs(grid, i, j);
                }
            }
        
        return ret;
    }
    
    void bfs(vector<vector<char>>& grid, int i, int j) {
        queue<vector<int> > q;
        
        q.push({i,j});
        grid[i][j] = '0';
        while (!q.empty()) {
            i = q.front()[0], j = q.front()[1];
            q.pop();  // 当前节点出队
                      // 当前节点的四周节点依次入队
            if (i > 0 && grid[i-1][j] == '1') {
                q.push({i-1,j});
                grid[i-1][j] = '0';
            }
            if (i < n-1 && grid[i+1][j] == '1') {
                q.push({i+1,j});
                grid[i+1][j] = '0';
            }
            if (j > 0 && grid[i][j-1] == '1') {
                q.push({i,j-1});
                grid[i][j-1] = '0';
            }
            if (j < m-1 && grid[i][j+1] == '1') {
                q.push({i,j+1});
                grid[i][j+1] = '0';
            }
        }
    }
};

总结：dfs比较容易实现而且效率更高。