My 12ms c++ solution


  • 2
    Z
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int row = board.size();
            if(row <= 2)
                return;
            int col = board[0].size();
            for(int i = 0; i < row; i ++){
                if(board[i][0] == 'O')
                    populate(board, i, 0);
                if(board[i][col-1] == 'O')
                    populate(board, i, col-1);
            }
            for(int i = 0; i < col; i ++){
                if(board[0][i] == 'O')
                    populate(board, 0, i);
                if(board[row-1][i] == 'O')
                    populate(board, row-1, i);
            }
            for(int i = 0; i < row; i ++){
                for(int j = 0; j < col; j ++){
                    if(board[i][j] == '*')
                        board[i][j] = 'O';
                    else
                        board[i][j] = 'X';
                }
            }
        }
        void populate(vector<vector<char>>& board, int x, int y){
            board[x][y] = '*';
            if(x > 1 && board[x-1][y] == 'O')
                populate(board, x-1, y);
            if(x < board.size()-1 && board[x+1][y] == 'O')
                populate(board, x+1, y);
            if(y > 1 && board[x][y-1] == 'O')
                populate(board, x, y-1);
            if(y < board[0].size()-1 && board[x][y+1] == 'O')
                populate(board, x, y+1);
        }
    };

  • 1
    B

    May I ask why you use if(x > 1 && board[x-1][y] == 'O') instead of if(x >= 1 && board[x-1][y] == 'O')?

    I have tried, >= will not get ac really. But I don't know why...............


  • 0
    Z

    I used x >= 1 at first and got runtime error. I am really confused about that too! I hope someone can give an answer.


  • 0
    B

    haha~~It's really smart of you to change x>=1 to x>1 when got runtime error.


  • 0
    Y

    I am so confused about this too! It would be great if someone can give me an answer...


  • 0
    E

    Well I got the same annoying problem, and I finally figured out that it's because of stack overflow. You can also try to change board.size()-1 to board.size()-2, that will pass the test cases too, but you need to cast board.size() to int, otherwise it will also fail when the size is 1 because size() is unsigned number. I think more general way to solve the problem is to implement DFS iteratively or use BFS as the other thread says.


Log in to reply
 

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