# Why is me C++ DFS solution Runtime Error at a case when submitting but passed when running?

• When I submitted it, it fails at the case with a large matrix with Runtime Error but when I ran with this case it gave correct result. I wonder whether it's because the space cost of the recursion. Can anyone give a exact reason?

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
helper(board, i, j);
}
}
// change all 'Y's to 'O's
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
board[i][j] = board[i][j] == 'Y' ? 'O' : board[i][j];
}
}

}

bool helper(vector<vector<char>>& board, int i, int j) {
if (i < 0 || j < 0 || i > board.size() - 1 || j > board[0].size() - 1 || board[i][j] == 'Y') { // reach to the edge
return true;
}
if (board[i][j] == 'X') {
return false;
}
board[i][j] = 'X';
bool res = helper(board, i - 1, j) || helper(board, i + 1, j) || helper(board, i, j - 1) || helper(board, i, j + 1);
if (res) {
board[i][j] = 'Y'; // if res is true, meaning this one is not surrounded, so set it to 'Y'
}
return res;
}
};``````

• I have the exact same problem with u

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.empty())
return;
vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));

for(int r = 0;r<board.size();r++){
for(int c =0; c<board[r].size();c++){
if(board[r][c] =='O')
if_safe(board,visited,r,c);
}
}
}
private:
bool if_safe(vector<vector<char>>& board, vector<vector<bool>> &visited,int r,int c){
if(r == board.size()||c == board[0].size()|| c == -1|| r == -1)
return true;

if(board[r][c] == 'X' || visited[r][c] == true)
return false;
visited[r][c] = true;

if(if_safe(board,visited,r+1,c)||if_safe(board,visited,r,c+1)||if_safe(board,visited,r-1,c)||if_safe(board,visited,r,c-1)){
return true;
}
else{
board[r][c] ='X';
return false;
}
}
};
``````

Anyone could help us?

• Maybe due to recursion? Maybe the size of the recursion stack is so large when using DFS? I am assuming that is the case, since this is what happened to me, until I change it to an iterative BFS.

• I have the same problem as you.

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