Concise 12ms C++ DFS solution


  • 7
    K

    First check all surrounding rows columns find those 'O' and their neighbors that are also 'O', make them to some other character like '1'. then traverse the whole board, now the 'O' left need to be turned to 'X', and those marked '1' turned back to 'O'

    like this:

    X X X X        X X X X         X X X X
    X O O X  --->  X O O X   --->  X X X X
    X X O X        X X O X         X X X X
    X O X X        X 1 X X         X O X X
    

    code:

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if (board.empty()) return;
            int row = board.size(), col = board[0].size();
            for (int i = 0; i < row; ++i) {
                check(board, i, 0);             // first column
                check(board, i, col - 1);       // last column
            }
            for (int j = 1; j < col - 1; ++j) {
                check(board, 0, j);             // first row
                check(board, row - 1, j);       // last row
            }
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < col; ++j)
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    else if (board[i][j] == '1') board[i][j] = 'O';
        }
        
        void check(vector<vector<char>>& board, int i, int j) {
            if (board[i][j] == 'O') {
                board[i][j] = '1';
                if (i > 1) check(board, i - 1, j);
                if (j > 1) check(board, i, j - 1);
                if (i + 1 < board.size()) check(board, i + 1, j);
                if (j + 1 < board[0].size()) check(board, i, j + 1);
            }
        }
    };

  • 0
    W

    I wondering in function check why it's if (i > 1) check(board, i - 1, j) rather than i>0, why don't check element of row 1?


  • 0
    M

    I also wonder to know the reason


  • 0
    M

    And if I change the condition to i>0,then there will be a runtime error!!!


  • 2
    M

    Oh, I think maybe I have known the reason. It is the recursion that leads to the runtime error. In order to decrease the recursion times, we don't need to check the outside boarder. So i>1,j>1,i+2<board.size(),and j+2<board[0].size().This platform has a limited stack storage.


  • 0

    This is the best one I've saw.


  • 0
    S

    @MHHNDL The error is so ambiguous, I spent a lot of time to check, until I find your posts.


  • 0
    L

    @ssq The platform is so stupid! Me, too. I spent quite some time to debug that runtime error.


  • 0
    G

    @lanshan317 So did I. I thought I was visiting the memory out of the boundary.


  • 0
    O

    @MHHNDL said in Concise 12ms C++ DFS solution:

    the recursion that leads to the runtime error. In order to decrease the recursion
    what if dfs is like this? still run error, i'm confused
    void dfs(vector<string>& board,int i, int j)
    {
    if (i < 0 || i >= board.size()) return;
    if (j < 0 || j >= board[0].size()) return;

    if (board[i][j] == 'X'||board[i][j] == '$') return;
    board[i][j] = '$';
    
    dfs(board,  i - 1,j);//上
    dfs(board, i + 1, j);//下
    dfs(board, i, j - 1);//左
    dfs(board, i, j + 1);//右
    

    }


Log in to reply
 

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