題目

給定一個2維陣列，1代表是土地，0代表是海，請計算有多少個小島。

Deep First Search (DFS)

是一種用來遍歷樹(tree)或圖(graph)的演算法。
以樹來說由樹的根來開始搜尋，先搜尋左子節點，並盡可能深的搜索，直到該節點不能再往下，便回朔(Backtracking)到前一個節點，重複探尋直到達成退出條件或遍歷完整棵樹
以圖來說相同。選某一點當作起點，先探尋邊(edge)上未搜尋的一點(vertex)，並儘可能深的搜索，直到該點的邊上點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的點，直到達成退出條件或遍歷整個圖。

解法

我們能將2維陣列想像成一張圖並使用DFS。從(0,0)往右往下，當遇到1時，代表出現了土地，必有一個小島，
那利用以出現1的這個點當作起點，利用DFS將這個島所有的土地遍歷，並用0(海)把它淹沒掉，避免重複遇到，以為是沒算過的小島，如此循環到(row,col)為止結束便可計算有多少小島。

Code

class Solution {
public:
    
    void dfs(vector<vector<char>>& graph,int row,int col){

        if(graph[row][col] == '1') {
            graph[row][col] = '0';  //用海淹沒
            
            if(row >=1) {
                dfs(graph,row-1,col); //往上探
            }
            
            if(row <graph.size()-1) {
                dfs(graph,row+1,col); //往下探
            }
            
            if(col >= 1) {
                dfs(graph,row,col-1); //往左探
            }
            
            if(col < graph[0].size()-1) {
                dfs(graph,row,col+1); //往右探
            }
        }

    }
    
    
    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'){
                    dfs(grid,i,j); //以(i,j)作為起點，進行dfs
                    ans++;         //小島數加1
                }
            }
        }
        return ans;
    }
};