Accepted 14ms DFS c++ solution and 16ms BFS c++ solution.


  • 6

    Please pay special attention to the comment in the solutions!

    DFS, 14ms:

    class Solution {
    public:
        void solve(std::vector<std::vector<char> > &board) {
            if (board.empty())
                return;
            rows = static_cast<int>(board.size());
            cols = static_cast<int>(board[0].size());
            if (rows < 3 || cols < 3)
                return;
            for (int col = 0; col < cols; ++col) {
                if (board[0][col] == 'O')
                    solveDFS(board, 0, col);
                if (board[rows - 1][col] == 'O')
                    solveDFS(board, rows - 1, col);
            }
            for (int row = 1; row < rows - 1; ++row) {
                if (board[row][0] == 'O')
                    solveDFS(board, row, 0);
                if (board[row][cols - 1] == 'O')
                    solveDFS(board, row, cols - 1);
            }
            for (int row = 0; row < rows; ++row)
                for (int col = 0; col < cols; ++col) {
                    if (board[row][col] == 'O')
                        board[row][col] = 'X';
                    else if (board[row][col] == 'N')
                        board[row][col] = 'O';
                }
        }
    private:
        int rows;
        int cols;
        void solveDFS(std::vector<std::vector<char> > &board, int i, int j) {
            board[i][j] = 'N';
            // no need to consider the peripheral border, so the condition
            // is i > 1, i < rows - 2, not i > 0, i < rows - 1.
            //
            // if use i > 0, i < rows - 1, DFS solution will get a Runtime Error, confusing!
            if (i > 1 && board[i - 1][j] == 'O')
                solveDFS(board, i - 1, j);
            if (i < rows - 2 && board[i + 1][j] == 'O')
                solveDFS(board, i + 1, j);
            if (j > 1 && board[i][j - 1] == 'O')
                solveDFS(board, i, j - 1);
            if (j < cols - 2 && board[i][j + 1] == 'O')
                solveDFS(board, i, j + 1);
        }
    };
    

    BFS, 16ms:

    class Solution {
    public:
        void solve(std::vector<std::vector<char> > &board) {
            if (board.empty())
                return;
            rows = static_cast<int>(board.size());
            cols = static_cast<int>(board[0].size());
            if (rows < 3 || cols < 3)
                return;
            for (int col = 0; col < cols; ++col) {
                if (board[0][col] == 'O')
                    solveBFS(board, 0, col);
                if (board[rows - 1][col] == 'O')
                    solveBFS(board, rows - 1, col);
            }
            for (int row = 1; row < rows - 1; ++row) {
                if (board[row][0] == 'O')
                    solveBFS(board, row, 0);
                if (board[row][cols - 1] == 'O')
                    solveBFS(board, row, cols - 1);
            }
            for (int row = 0; row < rows; ++row)
                for (int col = 0; col < cols; ++col) {
                    if (board[row][col] == 'O')
                        board[row][col] = 'X';
                    else if (board[row][col] == 'N')
                        board[row][col] = 'O';
                }
        }
    private:
        int rows, cols;
        void solveBFS(std::vector<std::vector<char> > &board, int i, int j) {
            board[i][j] = 'N';
    		std::queue<std::pair<int, int> > que;
            que.push(std::make_pair(i, j));
            while (!que.empty()) {
    			int row = que.front().first, col = que.front().second;
                que.pop();
                // no need to consider the peripheral border, so the condition
                // is i > 1, i < rows - 2, not i > 0, i < rows - 1.
                //
                // if use i > 0, i < rows - 1, BFS solution will be accepted too.
                if (row > 1 && board[row - 1][col] == 'O') {
                    board[row - 1][col] = 'N';
                    que.push(std::make_pair(row - 1, col));
                }
                if (row < rows - 2 && board[row + 1][col] == 'O') {
                    board[row + 1][col] = 'N';
                    que.push(std::make_pair(row + 1, col));
                }
                if (col > 1 && board[row][col - 1] == 'O') {
                    board[row][col - 1] = 'N';
                    que.push(std::make_pair(row, col - 1));
                }
                if (col < cols - 2 && board[row][col + 1] == 'O') {
                    board[row][col + 1] = 'N';
                    que.push(std::make_pair(row, col + 1));
                }
            }
        }
    };

  • 0
    R

    If your dfs code crash on large scale input, it may be the stack overflow issue.


  • 0

    As the comment in my DFS solution, if use i > 0, i < rows - 1, DFS solution will get a stack overflow issue in LeetCode, but if use i > 1, i < rows - 2, it will be accepted.

    Do you have any idea to improve the DFS solution?


  • 0
    C

    The stack overflow issue is resolved because you limit the range for each DFS.

    But it is still confusing because the same "problematic" DFS in problem Number of Islands can work correctly.

    https://leetcode.com/problems/number-of-islands/


  • 0
    R

    Your dfs solution still may cause stack over flow.
    see my answer here:
    https://leetcode.com/discuss/42445/a-really-simple-and-readable-c-solution,only-cost-12ms


  • 0

    Your DFS helps a lot! Thanks for your sharing!


Log in to reply
 

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