寬度優先搜尋

LeetCode 200

兩個思路：深度搜尋或者并查集。

思路一：DFS  依次通路每一個點, 如果是'1'就進行DFS搜尋, 通路過的地方可以改變他的值, 防止再次通路.

class Solution {
public:
    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]!='1') return;
        grid[i][j] = '2';
        DFS(grid, i+1, j);
        DFS(grid, i-1, j);
        DFS(grid, i, j+1);
        DFS(grid, i, j-1);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        int cnt = 0, m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
            for(int j =0; j < n; j++)
                if(grid[i][j] == '1')
                {
                    cnt++;
                    DFS(grid, i, j);
                }
        return cnt;
    }
};           

思路二：并查集

class Solution {  
public:  
    int find(int k, vector<int>& u){  
        return k == u[k] ? k : u[k] = find(u[k],u);  
    }  
    int numIslands(vector<vector<char>>& grid) {  
        int res = 0;  
        int m = grid.size();  
        if (!m) return 0;  
        int n = grid[0].size();  
        if (!n) return 0;  
        vector<int>us(grid.size()*grid[0].size());  
        //從右下角開始周遊  
        for (int i = m - 1; i >= 0; i--)  
            for (int j = n - 1; j >= 0; j--){  
                if (grid[i][j] != '0'){  
                    int k = i*n + j;  
                    //并查集  
                    int s = i != m - 1 && grid[i+1][j] != '0' ? find(k + n, us) : 0;  
                    int t = j != n - 1 && grid[i][j+1] != '0' ? find(k + 1, us) : 0;  
                    if (s == t){  
                        if (s) us[k] = s;  
                        else { us[k] = k; res++; }  
                    }  
                    else{  
                        if (!s) us[k] = t;  
                        else if (!t) us[k] = s;  
                        else{ us[k] = us[s] = us[t] = max(us[s], us[t]); res--; }  
                    }  
                }  
            }  
        return res;  
    }     
};