# A review of all solutions

• 1.dfs

``````    int numIslands(vector<vector<char>>& grid) {
int res=0;
for(int i=0;i<grid.size();i++) for(int j=0;j<grid[0].size();j++) res+=dfs(i,j,grid);
return res;
}
bool dfs(int r, int c, vector<vector<char>>& grid) {
if(r<0 || r== grid.size() || c<0 || c== grid[0].size() || grid[r][c]=='0') return 0;
grid[r][c]='0';
char dir[]={-1,0,1,0,-1};
for(int i=0; i<4; i++) dfs(r+dir[i],c+dir[i+1],grid);
return 1;
}
``````
1. bfs
``````    int numIslands(vector<vector<char>>& grid) {
int res=0;
for(int i=0;i<grid.size();i++) for(int j=0;j<grid[0].size();j++) res+=bfs(i,j,grid);
return res;
}
bool bfs(int r, int c, vector<vector<char>>& grid) {
if(grid[r][c]=='0') return 0;
char dir[]={-1,0,1,0,-1};
queue<pair<int,int>> q({pair<int,int>(r,c)});
while(!q.empty()) {
auto &p = q.front();
q.pop();
int x = p.first, y = p.second;
if(x<0 || x== grid.size() || y<0 || y== grid[0].size() ||grid[x][y]=='0') continue;
grid[x][y]='0';
for(int i=0; i<4; i++) q.push(pair<int,int>(x+dir[i],y+dir[i+1]));
}
return 1;
}
``````
1. union find
``````    int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
int r = grid.size(), c = grid[0].size(), count=r*c;
vector<int> id(r*c);
iota(id.begin(),id.end(),0);
char dir[] = {-1,0,1,0,-1};
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) {
if(grid[i][j]=='0') {
count--;
continue;
}
int rt = root(i*c+j,id);
for(int k=0;k<4;k++) {
int x = i+dir[k], y = j+dir[k+1];
if(x<0||x==r||y<0||y==c||grid[x][y]=='0') continue;
int rtn = root(x*c+y,id);
if (rt != rtn) {
id[rtn] = rt;
count--;
}
}
}
return count;
}
int root(int i, vector<int> &id) {
while(id[i]!=i) i=id[i]=id[id[i]];
return i;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.