###### tags: `LeetCode` `Medium` `DFS` `Recursion`
# LeetCode #200 [Number of Islands](https://leetcode.com/problems/number-of-islands/)
### (Medium)

給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，並且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

---

遍歷每一個元素, 若值為'1'(島嶼), 則將島嶼數量+1, 並使用DFS探索周圍, 找出與該點連接的陸地, 並把陸地改為水(1變成0)。如此一來, 整個島嶼都會消失, 就不必擔心其他島嶼探索時會遇到。

當探索到最後一個元素時, 整個數組都應該為0, 此時已探索完全部島嶼, 回傳島嶼數量即可。

DFS探索時的終止條件為越界或是探索到水('0'), 這樣可以確保探索時只會找到與開始點相鄰的陸地。

---

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