# Solution by DasongLi

• #### Approach #1 Depth First Search [Accepted]

Intuition

To traverse the whole islands, we use the Depth First Search to traverse the input matrix. We use one Depth First Search to traverse all the connected points, which combine to be one island. Using this method to traverse other points which have not been visited, We can get the number of the islands and traverse all the islands.

Algorithm

• Adding another matrix called `vector<vector<int>>& visited` to represent the states of all the points. All the initial values are zero.
• we have a function `void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited)` . The target of this function is to use `depth first search` to traverse all the connected points to get one island. After visited one point, this point's state changes to 1.
• boundary check is `if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size())`
• In the function `int numIslands(vector<vector<char>>& grid)`, we invoke the `dfs` function for the points whose states are 0

c++

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size()==0 or grid[0].size() == 0) return 0;
int i,j,k,l;
int width = grid.size(),height = grid[0].size();
vector<vector<int>> visited;
for (i=0;i<width;i++) {
vector<int> tmp;
for (j=0;j<height;j++) tmp.push_back(0);
visited.push_back(tmp);
}
int res = 0;
for (i=0;i<width*height;i++) {
j = i / height; k = i % height;
if (visited[j][k] == 0 and grid[j][k] == '1') {
dfs(j,k,grid,visited);
res ++;
}
}
return res;
}
private:
void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited) {
if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) return;
if (visited[x][y] == 1) return;
if (grid[x][y] == '0') return;
visited[x][y] = 1;
dfs(x+1,y,grid,visited);
dfs(x-1,y,grid,visited);
dfs(x,y+1,grid,visited);
dfs(x,y-1,grid,visited);
}
};
``````

Complexity Analysis

• Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
• Space complexity : O(1). we use `&` which means reference to achieve the dfs method, constant extra space is used.

#### Approach #2 Depth First Search and deleting the state matrix [Accepted]

Intuition

The core idea is similar to Approach #1, but it delete `vector<vector<int>>& visited` and change the `vector<vector<char>>& grid` to represent the states of points;

Core Ideas

• Delete the codes about `vector<vector<int>>& visited` , which will decrease the space and time to some extend.
• The values of the `vector<vector<char>>& grid` are representing the states of points. Zero and one are all the same. But two means the state of the points which has been visited and its original value is one.
• Other methods is similar to Approach #1.

c++

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size()==0 or grid[0].size() == 0) return 0;
int i,j,k,l;
int width = grid.size(),height = grid[0].size();
/*vector<vector<int> > visited;
for (i=0;i<width;i++) {
vector<int> tmp;
for (j=0;j<height;j++) tmp.push_back(0);
visited.push_back(tmp);
}*/
int res = 0;
for (i=0;i<width*height;i++) {
j = i / height; k = i % height;
if (grid[j][k] == '1') {
dfs(j,k,grid);
res ++;
}
}
return res;
}
private:
void dfs(int x, int y, vector<vector<char>>& grid) {
if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) return;
if (grid[x][y] == '0' or grid[x][y] == '2') return;
grid[x][y] = '2';
dfs(x+1,y,grid);
dfs(x-1,y,grid);
dfs(x,y+1,grid);
dfs(x,y-1,grid);
}
};
``````

Complexity Analysis

• Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
• Space complexity : O(1). we use `&` which means reference to achieve the dfs method, constant extra space is used.

#### Approach #3 Breadth First Search [Accepted]

Intuition

To traverse the whole islands, we use the Breadth First Search to traverse the input matrix. We use one Breadth First Search to traverse all the connected points, which combine to be one island. Using this method to traverse other points which have not been visited, We can get the number of the islands and traverse all the islands.

Algorithm

• we have a function `bfs(int x,int y,vector<vector<char>>& grid)` . The target of this function is to use `breadth first search` to traverse all the connected points to get one island. After visited one point, this point's state changes to 1.
• boundary check is `if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size())`
• In the function `int numIslands(vector<vector<char>>& grid)`, we invoke the `bfs` function for the points whose value in grid is one.

c++

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size()==0 or grid[0].size() == 0) return 0;
int i,j,k,l;
int width = grid.size(),height = grid[0].size();
/*vector<vector<int> > visited;
for (i=0;i<width;i++) {
vector<int> tmp;
for (j=0;j<height;j++) tmp.push_back(0);
visited.push_back(tmp);
}*/
int res = 0;
for (i=0;i<width*height;i++) {
j = i / height; k = i % height;
if (grid[j][k] == '1') {
dfs(j,k,grid);
res ++;
}
}
return res;
}
private:
void bfs(int x,int y,vector<vector<char>>& grid) {
queue<pair<int,int>> que;
que.push(pair<int,int>(x,y));
int xx[4] = {0,0,1,-1},yy[4] = {1,-1,0,0};
while (!que.empty()) {
pair<int,int> top = que.front(); que.pop();
int x = top.first, y = top.second;
if (x<0 || x>=grid.size() || y<0 || y>=grid[0].size()) continue;
if (grid[x][y] == '1') {
grid[x][y] = '2';
que.push(pair<int,int> (x+1,y));
que.push(pair<int,int> (x-1,y));
que.push(pair<int,int> (x,y-1));
que.push(pair<int,int> (x,y+1));
}

}
}
};
``````

Complexity Analysis

• Time complexity : O(n^2). The goal of our method is to traverse all the points with value one. Suppose the vector is n*n, the time complexity is O(n^2).
• Space complexity : O(n^2). We should put all the pairs into the queue, the space complexity is O(n^2).

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