# C++ use queue(BFS) TLE but stack(DFS) AC

• ``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.size() == 0){
return 0;
}
int m = grid.size();
int n = grid[0].size();
int ret = 0;
stack<pair<int, int>> s;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1' && !visited[i][j]){
ret++;
s.push(make_pair(i, j));
while(!s.empty()){
pair<int, int> cur = s.top();
s.pop();
int x = cur.first;
int y = cur.second;
visited[x][y] = true;
if((x+1) < m && grid[x+1][y] == '1' && !visited[x+1][y]){
s.push(make_pair(x+1, y));
}
if((x-1) >=0 && grid[x-1][y] == '1' && !visited[x-1][y]){
s.push(make_pair(x-1, y));
}
if((y+1) < n && grid[x][y+1] == '1' && !visited[x][y+1]){
s.push(make_pair(x, y+1));
}
if((y-1) >= 0 && grid[x][y-1] == '1' && !visited[x][y-1]){
s.push(make_pair(x, y-1));
}
}
}
}
}
return ret;
}
};
``````

This above one passed, but below got a TLE

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.size() == 0){
return 0;
}
int m = grid.size();
int n = grid[0].size();
int ret = 0;
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1' && !visited[i][j]){
ret++;
q.push(make_pair(i, j));
while(!q.empty()){
pair<int, int> cur = q.front();
q.pop();
int x = cur.first;
int y = cur.second;
visited[x][y] = true;
if((x+1) < m && grid[x+1][y] == '1' && !visited[x+1][y]){
q.push(make_pair(x+1, y));
}
if((x-1) >=0 && grid[x-1][y] == '1' && !visited[x-1][y]){
q.push(make_pair(x-1, y));
}
if((y+1) < n && grid[x][y+1] == '1' && !visited[x][y+1]){
q.push(make_pair(x, y+1));
}
if((y-1) >= 0 && grid[x][y-1] == '1' && !visited[x][y-1]){
q.push(make_pair(x, y-1));
}
}
}
}
}
return ret;
}
};
``````

The only difference of these two code is the stack and queue.

Assume that iterative is faster than recursive so I did not consider recursive(DFS) for now. How can I choose between BFS and DFS, in this case these two approaches should be the same.

Thanks in advance for any help.

• Mark, wait for the captain

• Say, there are three points in queue, [a, b, c]
When you handle a, you may have already visited b and c, but b and c have already in the queue.
Thus, your code will compute b and c repeatedly.

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