We love short code! 33 lines of code, 20 ms. C++

  • 3

    OJ must be quite mean (strict) about the solution of this problem. I have met all kinds of issue when trying to get a solution. Like TLE, MLE, and stack-overflow, etc. Having coding 3 or 4 solutions which could solve the problem (not all are efficient), I concluded that the below solution, the idea of which is referred to others, has the best time-efficiency, memory-efficieny, and easy-to-code virtues above all.

    The idea is not straight-forward to me, to be honest. It starts from boundaries, to find 'O' which shall not be flipped, which other fellows call it 'live'. Then flip all the rest 'O' which are not 'live'. And that's it!

    This this solution, I marked 'live' 'O' as '+' as other fellows, which is cool.

      class Solution {
          void solve(vector<vector<char>> &board)
            if (board.size() < 3 || board[0].size() < 3) return;
            for (int j = 0; j < board[0].size(); ++j)
              if (board[0][j] == 'O') bfs(board, 0, j);
              if (board[board.size()-1][j] == 'O') bfs(board, board.size()-1, j);
            for (int i = 0; i < board.size(); ++i)
              if (board[i][0] == 'O') bfs(board, i, 0);
              if (board[i][board[0].size()-1] == 'O') bfs(board, i, board[0].size()-1);
            for (auto &row : board)
              for (char &c : row)
                c = (c == '+') ? 'O' : 'X';
          void bfs(vector<vector<char>> &board, int i, int j)
            queue<pair<int, int>> q; q.emplace(i, j);
            board[i][j] = '+';
            while (!q.empty())
              i = q.front().first; j = q.front().second; q.pop();
              if (i > 0 && board[i-1][j] == 'O') {q.emplace(i-1, j);board[i-1][j]='+';}
              if (j < board[0].size()-1 && board[i][j+1] == 'O') {q.emplace(i, j+1);board[i][j+1]='+';}
              if (i < board.size()-1 && board[i+1][j] == 'O') {q.emplace(i+1, j);board[i+1][j]='+';}
              if (j > 0 && board[i][j-1] == 'O') {q.emplace(i, j-1);board[i][j-1]='+';}

  • 2

    So you call "if (j < board[0].size()-1 && board[i][j+1] == 'O') {q.emplace(i, j+1);board[i][j+1]='+';}"
    this kind of one line ?? I think you can't format this kind of code in company.

  • 0

    I can not agree with you for that though this way is not good but still acceptable in this circumstance.

  • 0

    Though acceptable, it doesn't look good/readable. It is kind of interesting to claim one line by concatenating lots of lines...

  • 1

    Agree with wjk20120522.
    When we count a line(in ACM or whatever), we should divide lines with statement. Think about compiler project. Mathematically or theoretically, "if (j < board[0].size()-1 && board[i][j+1] == 'O') {q.emplace(i, j+1);board[i][j+1]='+';}" is not one line. Moreover, no one write codes like this in company.

Log in to reply

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