[HELP] Why is my solution has runtime error on large input?


  • 0
    O

    Here is my DFS solution. However I got runtime error on large input. The annoy thing is I can't figure out what's wrong with the code? There is no invalid pointer here, no out of range exception. Also I've tested this on my own machine, which works just fine. Is there any problem with the OJ?

    class Solution {
    public:
        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> > visit(m, vector<bool>(n, false));
            for (int i = 0; i < m; ++i) {
                if (i == 0 || i == m - 1) {
                    for (int j = 0; j < n; ++j) {
                        dfsO(board, visit, i, j);
                    }
                } else {
                    dfsO(board, visit, i, 0);
                    dfsO(board, visit, i, n - 1);
                }
            }
            for (int i = 1; i < m - 1; ++i) {
                for (int j = 1; j < n - 1; ++j) {
                    if (board[i][j] == 'O' && !visit[i][j]) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
        
    private:
        void dfsO(const vector<vector<char> >& board, vector<vector<bool> >& visit, int i, int j) {
            if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
                return;
            }
            if (board[i][j] == 'X' || visit[i][j]) {
                return;
            }
            visit[i][j] = true;
            dfsO(board, visit, i + 1, j);
            dfsO(board, visit, i, j + 1);
            dfsO(board, visit, i - 1, j);
            dfsO(board, visit, i, j - 1);
        }
    };
    

Log in to reply
 

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