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


  • 3
    L

    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;
        }
    };

  • 0
    C

    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?


  • 0
    F

    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.


  • 0
    D

    I have the same problem as you.


Log in to reply
 

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