My code can not pass this longest case


  • 0
    9

    my algorithm: check the edges of board. if the point of edges is 'O', then set this point to 'V' and call dfs() recursively to set all points which connect to this point. After find all points which can not be changed to 'X', we set all 'V' points to 'O' and the rest to 'X'.

    my code cannot pass a very very long case. It reports run time error. But my code can pass almost all test cases. It is really weird. And if I use bfs, my code can pass all cases. But I think two methods are same.

      class Solution {
        public:
            typedef vector<vector<char> > BOARDTYPE;
            
            void solve(BOARDTYPE &board) {
                if (board.empty() || board[0].empty()) return;
                int N = board.size(), M = board[0].size();
                for (int i = 0; i < N; ++i)
                    for (int j = 0; j < M; ++j)
                        if (i == 0 || j == 0 || i == N-1 || j == M-1)
                            dfs(board, i, j); // you may call dfs or bfs here!
                for (int i = 0; i < N; ++i)
                    for (int j = 0; j < M; ++j)
                        board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
            }
            
             void dfs(BOARDTYPE &board, int row, int col) {
                int N = board.size(), M = board[0].size();
                if (row < 0 || row >= N || col < 0 || col >= M) return;
                if (board[row][col] != 'O') return;
                board[row][col] = 'V';
                dfs(board, row+1, col);
                dfs(board, row-1, col);
                dfs(board, row, col+1);
                dfs(board, row, col-1);
            }
        };

  • 0
    S

    Could you please format your code correctly? Select all code, then click {} button.


  • 11
    Z

    Stack overflow...That's the difference between dfs and bfs.


  • 0
    F

    I think it is because recursive dfs would take too much resource (too many calls which require space to store the calling state.)than hfs for long long case. considering one of test case with 200200 matrix, in worst case, the longest path (the number of calls)might take 200200 = 40,000 long. while with bfs, the maximal calls are about less than 400.


  • 0
    E

    it's not about DFS or BFS. if you use a stack to simulate the recursion of DFS everything's fine. you should put it like this: That's the difference between recursion and iteration.


  • 0
    L

    I agree with EDFward. It's not about DFS and BFS. It's about how you implement DFS. If you use Recursive, you will get Runtime Error. But if you implement DFS by stack, just like doing BFS by Queue, your code will get accepted.


  • 0
    I

    Yes, you can implement the dfs without recursive call, with a stack structure in heap memory, which normally allows more memory usage.
    But for this problem the memory used for dfs is significantly more than bfs. If you trace the grids you marked with dfs, it is a zigzag path. For bfs, it is the perimeter of the area.


  • 0
    X

    I concur. My iterative DFS passes.


  • 0
    R

    I tried to implement this with queue, but for me only when I use stack it works not the queue, so I think DFS is here better than BFS


Log in to reply
 

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