Better DFS but why does this give a runtime error?


  • 0
    F
    class Solution {
    public:
        bool validRowCol(int row, int col, int m, int n) {
            return row>=0 && row<=m-1 && col>=0 && col<=n-1; 
        }
        
        void dfs(vector<vector<char>>& board, int i, int j, int m, int n, vector<vector<bool>>& visited) {
            if (!validRowCol(i, j, m, n)) {
                return;
            }
    
            visited[i][j] = true;
            board[i][j] = 'Y';
    
            int row = i;
            int col = j+1;
            if (validRowCol(row, col, m, n) && board[row][col]!='X' && !visited[row][col]) {
                dfs(board, row, col, m, n, visited);
            }
            
            row = i;
            col = j-1;
            if (validRowCol(row, col, m, n) && board[row][col]!='X' && !visited[row][col]) {
                dfs(board, row, col, m, n, visited);
            }
            
            row = i-1;
            col = j;
            if (validRowCol(row, col, m, n) && board[row][col]!='X' && !visited[row][col]) {
                dfs(board, row, col, m, n, visited);
            }
            
            row = i+1;
            col = j;
            if (validRowCol(row, col, m, n) && board[row][col]!='X' && !visited[row][col]) {
                dfs(board, row, col, m, n, visited);
            }
        }
    
        void solve(vector<vector<char>>& board) {
            if (board.empty() || board[0].empty()) {
                return;
            }
            
            int m = board.size();
            int n = board[0].size();
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            bool mark = true;
            
            for (int i=0; i<m; ++i) {
                for (int j=0; j<n; ++j) {
                    if (board[i][j] == 'O' && !visited[i][j] && (i==0 || i==m-1 || j==0 || j==n-1)) {
                        dfs(board, i, j, m, n, visited);
                    }
                }
            }
            
            for (int i=0; i<m; ++i) {
                for (int j=0; j<n; ++j) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    
                    if (board[i][j] == 'Y') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    };
    

Log in to reply
 

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