前言

這一題200. Number of Islands也是top 100 liked的題目之一，是經典的DFS/BFS題目，一起來看看吧！

想法

想法很簡單，就是從第一個可以開始的左上角出發，上下左右走到不能走之後，再去找下一個還沒走過的點，直到整個地圖都檢查過為止。其實剛剛這句話就把解法講完了，只剩下怎麼實現而已。要完成這個解法，可以發現有一些需要紀錄的變數，第一個不用說一定是答案─目前的島嶼數量；第二個則是各點走過與否的紀錄，不然可能就會一直原地打轉到天荒地老。那程式部分的實現就可以採用DFS或BFS，Depth first search深度搜尋顧名思義就是順著可行的路不斷走下去，走到底再回去找另外一個可行的路走到底，一次就衝到最深；Bread first search則是記錄每個可行的下一步後，每個可能的路再走一步，就換走另一條路再試下一步；網路上說明這兩者差別的文章應該多到不行，也有說明兩者分別的特色與合適採用時機，並沒有特別難理解的概念，就不多說，不如直接看解法感受一下。
我採用的算是BFS，因為是使用queue，每次探索增加下一步可能後，下一個會從最早紀錄的點再下去探索。另外我記錄可行的候選點是用pair來存一維跟二維的index；紀錄探索過與否則直接套用原本的grid，把走過的也改成非陸地的'0'；從左上角開始找到出發點並探索完成後，再去找下一個陸地的部分，直到整個grid都變成'0'為止。
程式碼如下：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ans=0;
        // BFS: start from left top, keep lands to be discoverd in a queue
        queue<pair<int, int> > q;
        int x=0, y=0;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                // if not seen
                if(grid[i][j]!='0'){
                    q.push({i,j});
                    ++ans;
                    grid[i][j]='0';
                    //q.pop();
                }
                // search for all possible lands
                while(!q.empty()){
                    x=q.front().first;
                    y=q.front().second;
                    q.pop();
                    // if their neighbors could be reached
                    // up
                    if(x>0 && grid[x-1][y]!='0'){
                        q.push({x-1,y});
                        grid[x-1][y]='0';
                    }
                    // down
                    if(x<grid.size()-1 && grid[x+1][y]!='0'){
                        q.push({x+1,y});
                        grid[x+1][y]='0';
                    }
                    // left
                    if(y>0 && grid[x][y-1]!='0'){
                        q.push({x,y-1});
                        grid[x][y-1]='0';
                    }
                    // right
                    if(y<grid[0].size()-1 && grid[x][y+1]!='0'){
                        q.push({x,y+1});
                        grid[x][y+1]='0';
                    }


                }
            }
        }
        return ans;
    }
};

另外附上討論區別人寫的DFS版本可以做個參考~

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
  }
    int numIslands(vector<vector<char>>& grid) {
       int islands = 0; 
    int nr = grid.size();
    if(!nr) return 0; 
    int nc = grid[0].size();
    
    for(int r = 0; r < nr; r++)
    {
        for(int c = 0; c < nc; c++)
        {
            if(grid[r][c] == '1')
            {
                islands++;
                dfs (grid,r,c);
            }
        }
    }
        
    return islands; 
    }
};

結語

預計明日回歸每日挑戰，中秋連假快樂！