(LeetCode 200)Number of Islands(およびセット、DFS)

Q: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110 11010 11000 00000 Answer: 1
Example 2:
11000 11000 00100 00011 Answer: 3
大体、1と0からなる2次元文字の配列をあげます.1は陸地を表し、0は水を表します.水に囲まれた陸地を結ぶ領域の個数を聞く.
solution:この問題の構想は前のいくつかの問題とほぼ一致しており、DFS、BFSを使用して、調査集で解決することができます.Poj 2386 Lake Counting(DFSアルゴリズム)(LeetCode 130)Surrounded Regions(BFS)(LeetCode 130)Surrounded Regions
この問題の解法については、上の3つのリンクに詳しく紹介されていますが、ここではこの問題のコードを貼ればいいでしょう.DFSと検索セットのコードの2つの方法の時間消費は同じですが、あまり理想的ではありません.改善方法があれば教えてほしいです.DFSの再帰使用に感謝します.コードは簡潔にしてください.検索セット:

class Solution {
public:
    vector<int> UN;
    int count=0;
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0||grid[0].size()==0)return 0;
        int length = grid.size()*grid[0].size();
        int width = grid[0].size();
        UN = vector<int>(length,0);
        for(int i=0;iint x=i/width,y=i%width;
            if(grid[x][y]=='1')count++;
            UN[i]=i;
        }
        cout<for(int j=0;jint x=j/width,y=j%width;
            int down=x+1,right=y+1;
            if(down'1'&&grid[down][y]=='1')
             unionset(j,j+width);
            if(right0].size()&&grid[x][y]=='1'&&grid[x][right]=='1')
             unionset(j,j+1);
        }
        return count;
    }

    void unionset(int m,int n){
        int rootM=find(m);
        int rootN=find(n);
        if(rootM==rootN)return;
        UN[rootN]=rootM;
        //cout<
        count--;
    }

    int find(int p){
        while(p!=UN[p]){
            UN[p]=UN[UN[p]];
            p=UN[p];
        }
        return p;
    }
};

DFS再帰:

class Solution {
public:
    vector<vector<int>>visit;
    int px[4]={-1,1,0,0};
    int py[4]={0,0,-1,1};
    int count=0;
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0||grid[0].size()==0)return 0;
        visit = vector<vector<int>>(grid.size(),vector<int>(grid[0].size(),0));
        for(int i=0;ifor(int j=0;j0].size();j++){
            if(grid[i][j]=='0'||visit[i][j]==1)continue;
             count++;
            dfs(grid,i,j);
        };
        return count;
    }
    void dfs(vector<vector<char>>& grid,int m,int n){
        visit[m][n]=1;
        for(int i=0;i<4;i++){
            int x=m+px[i],y=n+py[i];
            if((x<0)||(x>=grid.size())||(y<0)||(y>=grid[0].size()))continue;
            if(visit[x][y]==1)continue;
            if(grid[x][y]=='0')continue;
            dfs(grid,x,y);
        }
    }
};