Surrounded Regions

来源：

原帖：https://oj.leetcode.com/problems/surrounded-regions/

题目：
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,
 X X X X
 X O O X
 X X O X
 X O X X
After running your function, the board should be:
 X X X X
 X X X X
 X X X X
 X O X X
Solution: Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).

代码：

 // rumtime error  
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') dfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') dfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') dfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') dfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
     
   void dfs(BOARDTYPE &board, int row, int col) {  
     int M = board.size(), N = board[0].size();  
     board[row][col] = 'V';  
     for (auto o : offset) {  
       int i = row + o.first, j = col + o.second;  
       if (i >= 0 && i < M && j >= 0 && j < N && board[i][j] == 'O') {  
         dfs(board, i, j);  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   
   void bfs(BOARDTYPE &board, int row, int col) {  
     if (board[row][col] != 'O') return;  
     int M = board.size(), N = board[0].size();  
     queue<pair<int, int> > q;  
     board[row][col] = 'V';  
     q.push({row, col}); // q.push({i, j}); pair对也可以使用{i, j} instead of make_pair(i,j)  
     while (!q.empty()) {  
       int i = q.front().first, j = q.front().second;  
       q.pop();  
       for (auto o : offset) {  
         int ii = o.first + i, jj = o.second + j;  
         if (ii >= 0 && ii < M && jj >= 0 && jj < N && board[ii][jj] == 'O') {  
           board[ii][jj] = 'V'; // update !!!   
           q.push({ii, jj});  
         }  
       }  
     }  
   }  
   
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     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);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
 };