DFS with off-by-one problem


  • 0
    S

    I just tried to solve this question with both BFS and DFS, and BFS worked while DFS failed.

    It's weird that, if I submitted this solution, I would get run-time error, however, if I copied the test case to costum testcase, it worked fine.

    I thought that my logic should be right, the process was similar to the BFS solution. Then I tried to compare the DFS one with my accepted solutoin, which was submitted several months ago, I found there was just an off-by-one problem. Here is my DFS solution with runtime error:

    class Solution {
    private:
        // change x< 0 and y < 0 to x < 1, y < 1
        bool check(vector<vector<char>>& board, int x, int y, int m, int n) {
            return !(x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O');
        }
        void dfs(vector<vector<char>>& board, int x, int y, int m, int n, vector<vector<int>>& dir) {
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (check(board, nx, ny,  m, n)) {
                    board[nx][ny] = '#';
                    dfs(board, nx, ny, m, n, dir);
                }
            }
        }
    public:
        void solve(vector<vector<char>>& board) {
            if (board.size() == 0 || board[0].size() == 0) return;
            int m = board.size(), n = board[0].size();
            vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            // Add all outside 'O' to our queue
            queue<pair<int, int>> q;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // Just need one of the bound
                    if (board[i][j] == 'O' && !(i != 0 && j != 0 && i != m - 1 && j != n - 1)) {
                        board[i][j] = '#';
                        dfs(board, i, j, m, n, dir);
                    }
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == '#') board[i][j] = 'O';
                    else if (board[i][j] == 'O') board[i][j] = 'X';
                }
            }
        }
    };
    

    After I changed

    x < 0 || y < 0

    to be

    x < 1 || y < 1

    in the boundary checking function, it was accepted. I understand that, since we will call the dfs from the boundary of the matrix, we no longer need to check it again, but how to explain the runtime error if I just want to check it again? Anyone have any idea?


Log in to reply
 

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