[LeetCode] Surrounded Regions-白红宇

This problem is not quite difficult (a typical BFS traversal of graph), though, its aceptance rate is relatively low. In fact, the key obstacle in passing this problem is how to reduce the number of checks and avoid the annoying TLE.

There is a nice idea in . In fact, all the surrounded regions will not contain an O on the boundary. This idea takes advantage of this observation and visit the board from O's on the boundary and mark them using another character, say, #. Finally, all the remaining O's are the surrounded regions and should be captured to X. The # regions simply need to be recovered to O.

I adopt the idea from the above link. And I include some minor optimizations. For example, I pass the queue toVisit to the update function to check and update the four neighbors together during the BFS. This turns out to reduce the running time from 28ms to 16ms.

The code is as follows.

1 class Solution { 2 public: 3     void solve(vector
     
      
       >& board) { 4         if (board.empty()) return; 5         int m = board.size(), n = board[0].size(); 6         for (int i = 0; i < m; i++) { 7             if (board[i][0] == 'O') 8                 mark(board, i, 0); 9             if (board[i][n - 1] == 'O')10                 mark(board, i, n - 1);11         }12         for (int j = 0; j < n; j++) {13             if (board[0][j] == 'O')14                 mark(board, 0, j);15             if (board[m - 1][j] == 'O')16                 mark(board, m - 1, j);17         }18         capture(board);19     }20 private:21     // Update neighbors22     void update(vector
       
        
         >& board, queue
         
          
           >& toVisit, int r, int c) {23 int m = board.size(), n = board[0].size();24 if (r - 1 >= 0 && board[r - 1][c] == 'O') {25 board[r - 1][c] = '#';26 toVisit.push(make_pair(r - 1, c));27 }28 if (r + 1 < m && board[r + 1][c] == 'O') {29 board[r + 1][c] = '#';30 toVisit.push(make_pair(r + 1, c));31 }32 if (c - 1 >= 0 && board[r][c - 1] == 'O') {33 board[r][c - 1] = '#';34 toVisit.push(make_pair(r, c - 1));35 }36 if (c + 1 < n && board[r][c + 1] == 'O') {37 board[r][c + 1] = '#';38 toVisit.push(make_pair(r, c + 1));39 }40 }41 // Mark non-surrounded regions42 void mark(vector
           
            
             >& board, int r, int c) {43 queue
             
              
                > toVisit;44 toVisit.push(make_pair(r, c));45 board[r][c] = '#';46 while (!toVisit.empty()) {47 int num = toVisit.size();48 for (int i = 0; i < num; i++) {49 pair
               
                 cur = toVisit.front();50 toVisit.pop();51 update(board, toVisit, cur.first, cur.second);52 }53 }54 }55 // Capture surrounded regions56 void capture(vector
                
                 
                  >& board) {57 int m = board.size(), n = board[0].size();58 for (int i = 0; i < m; i++) {59 for (int j = 0; j < n; j++) {60 if (board[i][j] == '#')61 board[i][j] = 'O';62 else board[i][j] = 'X';63 }64 }65 }66 };