C++ solution. I think my solution should work. But it failed in the 200-row test case. Anyone can help me with this?


  • 2
    Y
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            for(int i = 0; i < board.size(); i++)
                for(int j = 0; j < board[0].size(); j++)
                    if(board[i][j] == 'O')
                    {
                        vector<pair<int, int>> temp;
                        if(!dfs(board, temp, i, j))
                        {
                            for(int k = 0; k < temp.size(); k++)
                            {
                                board[temp[k].first][temp[k].second] = 'Z';
                            }
                        }
                    }
            for(int i = 0; i < board.size(); i++)
                for(int j = 0; j < board[0].size(); j++)
                    if(board[i][j] == 'Z')
                        board[i][j] = 'O';
        }
        bool dfs(vector<vector<char>>& board, vector<pair<int, int>>& all, int x, int y)
        {
            all.push_back(make_pair(x, y));
            board[x][y] = 'X';
            bool t1, t2, t3, t4;
            t1 = t2 = t3 = t4 = true;
            if(x-1 >= 0 && board[x-1][y] == 'O')
                t1 = dfs(board, all, x-1, y);
            if(y-1 >= 0 && board[x][y-1] == 'O')
                t2 = dfs(board, all, x, y-1);
            if(x+1 < board.size() && board[x+1][y] == 'O')
                t3 = dfs(board, all, x+1, y);
            if(y+1 < board[0].size() && board[x][y+1] == 'O')
                t4 = dfs(board, all, x, y+1);
            if(x == 0 || x == board.size()-1 || y == 0 || y == board[0].size()-1)
                return false;
            return t1 && t2 && t3 && t4;
        }
    };

  • 0

    My solution is similar to yours and I have the same problem.When I run my program online with the 200 lines test case ,it work well .But when I submit it ,it get a "run time error".


  • -1
    Y
    if(x-1 > 0 && board[x-1][y] == 'O') {// no equal
                board[x-1][y] = 'X'; //set first
                t1 = dfs(board, all, x-1, y);
    }
    if(y-1 > 0 && board[x][y-1] == 'O'){
                board[x][y-1] = 'X'; //set first
                t2 = dfs(board, all, x, y-1);
    }
    if(x+1 < board.size() && board[x+1][y] == 'O'){
                board[x+1][y] = 'X'; //set first
                t3 = dfs(board, all, x+1, y);
    }
    if(y+1 < board[0].size() && board[x][y+1] == 'O'){
                board[x][y+1] = 'X'; //set first
                t4 = dfs(board, all, x, y+1);
    }
    

  • 0

    @yin10 Format your code properly, please! Thank you! B.T.W. your suggestion is right.


  • 0

Log in to reply
 

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