6ms C++ Solution Beats 90% Submissions!


  • 0
    class Solution {
    public:
      void solve(vector<vector<char>>& board) {
        int row_size = board.size();
        if (!row_size)
          return;
        int col_size = board.front().size();
        //up down
        for (int i = 0; i < col_size; ++i) {
          _solve(board, 0, i);
          _solve(board, row_size - 1, i);
        }
        // left right
        for (int i = 0; i < row_size; ++i) {
          _solve(board, i, 0);
          _solve(board, i, col_size - 1);
        }
    
        for (int i = 0; i < row_size; ++i)
        for (int j = 0; j < col_size; ++j)
          if (board[i][j] == '$')
            board[i][j] = 'O';
          else
            board[i][j] = 'X';
      }
      void _solve(vector<vector<char>>& board, int i, int j) {
        if (board[i][j] != 'O')
          return;
        board[i][j] = '$';
        if (i > 0)
          _solve(board, i - 1, j);
        if (i < board.size() - 1)
          _solve(board, i + 1, j);
        if (j > 1) //can not explain if j > 0 , can not be accepted
          _solve(board, i, j - 1);
        if (j < board[0].size() - 1)
          _solve(board, i, j + 1);
      } 
    
    };
    

Log in to reply
 

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