# 200-Number of islands
###### tags: `Medium`
* Key:
1. BFS
a. 用兩個for-loop遍尋地圖上每個點，一遇到陸地(1)，就會將島嶼數量加一，
b.先將一個點放到Queue中，如果是陸地就開始檢查其上下左右是否在地圖中?、是否也為陸地?若為陸地就加入Queue中並改為海洋(0)，檢查完後，再將其從Queue中移除，直到Queue中沒有元素，代表搜尋完一個小島面積，以此類推遍尋所有陸地得到所有小島
2. DFS
a. 用兩個for-loop遍尋地圖上每個點，一遇到陸地(1)，就會將島嶼數量加一，
b. 將該陸地設為海洋(0)，以及為了避免將其他小島也設為海洋，所以檢查該陸地**上下左右**是否為陸地，是的話，也設成海洋，這樣島嶼數量加一前，就能先設成海洋。遇到海洋則繼續遍尋，直到遍尋完成整個地圖

3.BFS相較於DFS，可以避免地圖為大面積時，遞迴數量增大而產生的Stack overflow
## DFS Solution

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0;

        // 走過矩陣的所有 element，只要遇到島，就把島都消滅(即 '1' -> '0')
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    dfs(grid, m, n, i, j);
                }
            }
        }

        return islands;
    }

private:
    void dfs(vector<vector<char>>& grid, const int& m, const int& n, const int& i, const int& j) {
        if(grid[i][j] == '0') return;

        grid[i][j] = '0';

        if(i - 1 >= 0) { dfs(grid, m, n, i-1, j); }
        if(i + 1 < m)  { dfs(grid, m, n, i+1, j); }
        if(j - 1 >= 0) { dfs(grid, m, n, i, j-1); }
        if(j + 1 < n)  { dfs(grid, m, n, i, j+1); }
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0, offsets[] = {0, 1, 0, -1, 0};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    grid[i][j] = '0';

                    queue<pair<int, int>> todo;
                    todo.push({i, j});

                    while (!todo.empty()) {
                        pair<int, int> p = todo.front();
                        todo.pop();

                        for (int k = 0; k < 4; k++) {
                            int r = p.first + offsets[k], c = p.second + offsets[k + 1];
                            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
                                grid[r][c] = '0';
                                todo.push({r, c});
                            }
                        }
                    }
                }
            }
        }

        return islands;
    }
};