My accepted c++ solution (may be trivial)

• ``````class Solution {
public:
void contaminate(vector<vector<char> > &grid, int i, int j){
if(i>0&&grid[i-1][j]=='1'){
grid[i-1][j]='0';
contaminate(grid, i-1, j);
}
if(j>0&&grid[i][j-1]=='1'){
grid[i][j-1]='0';
contaminate(grid, i, j-1);
}
if(i<grid.size()-1&&grid[i+1][j]=='1'){
grid[i+1][j]='0';
contaminate(grid, i+1, j);
}
if(j<grid[0].size()-1&&grid[i][j+1]=='1'){
grid[i][j+1]='0';
contaminate(grid, i, j+1);
}
}
int numIslands(vector<vector<char>> &grid) {
int n=grid.size();
if(n==0) return 0;
int m=grid[0].size();

int cnt=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j]=='1'){
cnt++;
contaminate(grid, i, j);
}
}
}
return cnt;
}
};``````

• does this DFS?

• Share my code, kinda like disjoint-set ,but no searching function is needed

``````class Solution {
public:
int numIslands(vector<vector<char> >& grid) {
if (grid.empty()) return 0;
int row = grid.size(), col = grid[0].size();
int n = row*col;
int *father = new int[n];
int res = 0;

memset(father,-1,n*sizeof(int));

for (int i=0;i<row;i++)
for (int j=0;j<col;j++){
if (grid[i][j]=='1') {
if (i==0&&j==0){ father[0]=0;continue;}
if (i==0)
father[j] = grid[0][j-1]=='1'?father[j-1]:j;
else if (j==0)
father[i*col] = grid[i-1][0]=='1'?father[(i-1)*col]:(i*col);
else{
int temp = col*i+j;
int fup = father[temp-col];
int fleft = father[temp-1];

if (fup==-1&&fleft==-1)
father[temp] = temp;
else if (fup==-1&&fleft!=-1)
father[temp] = fleft;
else if (fup!=-1&&fleft==-1)
father[temp] = fup;
else{
if (fup!=fleft) father[max(fup,fleft)] = min(fup,fleft);
father[temp] = min(fup,fleft);
}
}
}
}

for (int i=0;i<n;i++)
if (father[i]==i)
res++;

delete[] father;

return res;
}
}; ``````

• Nice recursion in `contaminate`.

• your idea is to make an island disappear once find one, right?

• can you say the complexity please?

• Same idea, but more concise code:

`````` void DFS(vector<vector<char>>& grid, int i, int j){
if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
if('0' == grid[i][j]) return;
grid[i][j] = '0';
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) {
int counter = 0;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[i].size(); ++j)
if ('1' == grid[i][j])
{
++counter;
DFS(grid, i, j);
}
return counter;
}``````

• Maybe the code can be more clear:

``````class Solution
{
public:
int numIslands(vector<vector<char>>& grid)
{
if(grid.empty())
return 0;
const int m=grid.size();
const int n=grid[0].size();
int cnt=0;
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(dfsDetector(i,j,m,n,grid))
++cnt;
}
}
return cnt;
}
private:
bool dfsDetector(int i,int j,const int &m,const int &n,vector<vector<char>> &grid)
{
const static vector<vector<int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
const int dirCnt=dir.size();
if(i<0 || i>=m || j<0 || j>=n)
return false;
if(grid[i][j]=='1')
{
grid[i][j]='2';
for(int k=0;k<dirCnt;++k)
dfsDetector(i+dir[k][0],j+dir[k][1],m,n,grid);
return true;
}
else
return false;
}
};``````

• same idea, less cod and more clean

``````int numIslands(vector<vector<char>>& grid) {
const int row = grid.size();
if (row == 0) return 0;
const int col = grid[0].size();
int cnt = 0;
for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j) {
if (grid[i][j] == '1') {
cnt++;
dfs(grid, i, j);
}
}
return cnt;
}
void dfs(vector<vector<char>> &grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') return;
vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
grid[i][j] = '0';
for (auto dir : dirs) {
dfs(grid, i+ dir.first, j + dir.second);
}
}``````

• `O(nm)`: `n*m` for the initial calls to `contaminate` and the `contaminate` recursive calls will collectively clear all `'1'`s which cannot be no more than `n*m`.

• I think you should declare that `dirs` `static` (or outside the function) as it will be recreated on every `dfs` call, that is `row*col` times at worst.

• This post is deleted!

• Nice idea, but I think the interviewer is going to ask you to avoid updating the original grid.

• @animageofmine Do you mean the parameter is "const vector<vector<char>>& grid"?In that case,we can construct a new array whose type is bool[][] or deque<deque<bool>> to record the gird we have traversed.

• @tju_xu97 - don't we need {} braces with for loop? How does your code work without the braces?

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