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

解题思路：

1. 典型的DFS、BFS题目，遍历1的同时，把临近的节点链接节点为1的加入队列，然后依次把这些节点置为0。这样保证能遍历到的临近岛屿只计数一次

2. 用union find的方法，大致思路是利用这个算法，把临近的认为是同一个的join起来，这个后续再进一步讨论，

解法1的code 如下

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