问题：
给定一个m*n棋盘，由O和X填入。
将棋盘中被X包围的O转化成X。
说明：在四周边缘的O，以及和这些O相邻（上下左右相邻）的O，无法转化。其他的棋盘内部O皆可转化为X。
Example 1: Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] Explanation: Surrounded regions should not be on the border, which means that any ‘O‘ on the border of the board are not flipped to ‘X‘. Any ‘O‘ that is not on the border and it is not connected to an ‘O‘ on the border will be flipped to ‘X‘. Two cells are connected if they are adjacent cells connected horizontally or vertically. Example 2: Input: board = [["X"]] Output: [["X"]] Constraints: m == board.length n == board[i].length 1 <= m, n <= 200 board[i][j] is ‘X‘ or ‘O‘.
解法：BFS
queue：保存当前一层遍历中，遇到的O。（从四边缘开始，每相邻一层，为新的一层）
对当前格子：无法转化的对象：将board上标记为 $
若相邻为O 且 该格子没有访问过，则，q.push（{i, j}）
最后遍历board，若标记为$,则填入O，其他的O填入X。
代码参考：
1 class Solution { 2 public: 3 bool isValid(int i, int j, int m, int n) { 4 if(i<0 || j<0 || i>=m || j>=n) return false; 5 return true; 6 } 7 void solve(vector<vector<char>>& board) { 8 int m = board.size(), n = board[0].size(); 9 vector<vector<bool>> visited(m,vector<bool>(n,0)); 10 queue<vector<int>> q; 11 vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}}; 12 for(int i=0; i<m; i++) { 13 if(board[i][0] == ‘O‘) { 14 q.push({i, 0}); 15 visited[i][0] = 1; 16 } 17 if(board[i][n-1] == ‘O‘) { 18 q.push({i, n-1}); 19 visited[i][n-1] = 1; 20 } 21 } 22 for(int j=0; j<n; j++) { 23 if(board[0][j] == ‘O‘) { 24 q.push({0, j}); 25 visited[0][j] = 1; 26 } 27 if(board[m-1][j] == ‘O‘) { 28 q.push({m-1, j}); 29 visited[m-1][j] = 1; 30 } 31 } 32 while(!q.empty()) { 33 int sz = q.size(); 34 for(int k=0; k<sz; k++) { 35 vector<int> cur = q.front(); 36 q.pop(); 37 board[cur[0]][cur[1]] = ‘$‘; 38 for(vector<int> d:dir) { 39 int i = cur[0]+d[0], j = cur[1]+d[1]; 40 if(isValid(i, j, m, n) && visited[i][j] != 1 && board[i][j] == ‘O‘) { 41 q.push({i, j}); 42 visited[i][j] = 1; 43 } 44 } 45 } 46 } 47 for(int i=0; i<m; i++) { 48 for(int j=0; j<n; j++) { 49 if(board[i][j] == ‘$‘) board[i][j] = ‘O‘; 50 else if(board[i][j] == ‘O‘) board[i][j] = ‘X‘; 51 } 52 } 53 return; 54 } 55 };
原文：https://www.cnblogs.com/habibah-chang/p/14446385.html