image.png

思路1：DFS

  1. 第一步，先把所有边界，以及和边界相关的格子，统统标记为A
  2. 第二步，把所有内部的O统统变成X，但是所有的A统统变成O
  3. 所以，问题的关键在于，如果找出所有边界上的字符。

  4. 第一种找到和边界字符连通的字符的思路就是DFS的做法。

    思路2：BFS

  5. 大的思路延续DFS的办法

  6. 改变之处在于，如果通过BFS的策略，找到所有边缘上的’O’和它的兄弟姐妹
  7. 将当前扫描到的位置{x,y}记为root根节点
  8. 上下左右的四个位置，符合条件的位置，记为下一层的节点，然后以此类推。

  9. 注意，一旦进入队列之后，需要立即改变标记为’A’,否则会出现多次重复进入队列的问题。

    代码2：

    1. class Solution {
    2. public:
    3.  int move_pos[4] = {1, 0, -1, 0};
    4.  void bfs(vector<vector<char>>& board, int x, int y, int row, int col) {
    5.      board[x][y] = 'A';
    6.      queue<pair<int,int>> q;
    7.      q.push({x, y});
    9.      while (!q.empty()) {
    10.          int cur_level_size = q.size();
    11.          for (int i = 0; i < cur_level_size; ++i) {
    12.              pair<int,int> cur_pos = q.front();
    13.              int cur_x = q.front().first, cur_y = q.front().second;
    14.              q.pop();
    16.              for (int i = 0; i < 4; ++i) {
    17.                  int next_x = cur_x + move_pos[i];
    18.                  int next_y = cur_y + move_pos[(i + 1) % 4];
    19.                  if (next_x < 0 || next_x >= row || next_y < 0 || next_y >= col || board[next_x][next_y] != 'O' ) {
    20.                      continue;
    21.                  } else {
    23.                  }
    25.              }
    26.          }
    27.      }
    28.  }
    30.  void solve(vector<vector<char>>& board) {
    31.      int row = board.size();
    32.      int col = board[0].size();
    34.      // 第1步，将所有边上的O，和它的兄弟姐妹，统统标记成A
    35.      for (int i = 0; i < row; ++i) {
    36.          if(board[i][0] == 'O') 
    37.              bfs(board, i, 0, row, col);
    38.          if(board[i][col - 1] == 'O') 
    39.              bfs(board, i, col - 1, row, col);
    40.      } 
    42.      for (int i = 0; i < col; ++i) {
    43.          if (board[0][i] == 'O')
    44.              bfs(board, 0, i, row, col);
    45.          if (board[row - 1][i] == 'O')
    46.              bfs(board, row - 1, i, row, col);
    47.      }
    49.      // 第2步，将所有O变成X
    50.      for (int i = 0; i < row; ++i) {
    51.          for (int j = 0; j < col; ++j) {
    52.              if (board[i][j] == 'A') {
    53.                  board[i][j] = 'O';
    54.              } else if (board[i][j] == 'O') {
    55.                  board[i][j] = 'X';
    56.              }
    57.          }
    58.      }
    60.  }
    61. };

    两个细节：

  10. 如何改变方向：

    1. int move_pos[4] = {1, 0, -1, 0};
    2. int next_x = cur_x + move_pos[i];
    3. int next_y = cur_y + move_pos[(i + 1) % 4];

  11. 如何避免重复进入队列（一进入队列立即标记）

    1. q.push({next_x, next_y});
    3. // 进入队列之后，立即改变标号，这样可以避免重复进入队列的问题
    4. board[next_x][next_y] = 'A';

    思路3：并查集

  • 并查集，3个步骤
  • 对于所有位于边界上的点，和“特殊点”放到一组
  • 对于所有内部的点，和上下左右可以连通的点放到一起
  • 如果内部和边界联系上了，也就是和“特殊点”在一起，那么，就变成‘O’，如果和边界上的点联系不到一起，那么就是’X’
  • 小trick：利用node(i, j) = i * col + j将二维的点映射成一维的数字

    代码3：并查集

    ```cpp class Solution { private: int row, col; unordered_map fa, r; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};

public: void init(int n) { for (int i = 0; i <= n; i++) { fa[i] = i; r[i] = 1; } }

  1. int find(int x) {
  2.     if (fa[x] != x) {
  3.         fa[x] = find(fa[x]);
  4.     }
  5.     return fa[x];
  6. }
  8. void merge(int i, int j) {
  9.     int x = find(i), y = find(j);
  10.     if (x != y) {
  11.         if (r[x] <= r[y]) {
  12.             fa[x] = y;
  13.         } else {
  14.             fa[y] = x;
  15.         }
  17.         if (r[x] == r[y]) {
  18.             r[y] += 1;
  19.         }
  20.     }
  21. }
  23. // 2维坐标到1维数字
  24. int node(int i, int j) {
  25.     return i * col + j;
  26. }
  28. bool check(int i, int j) {
  29.     if (0 <= i && i <= row - 1 && 0 <= j && j <= col - 1) {
  30.         return true;
  31.     }
  33.     return false;
  34. }
  36. void solve(vector<vector<char>>& board) {
  37.     // 并查集，3个步骤
  38.     // 1. 对于所有位于边界上的点，和特殊点放到一起
  39.     // 2. 对于所有内部的点，和上下左右可以连通的点放到一起
  40.     // 3. 如果内部和边界联系上了，也就是和“特殊点”在一起，那么，就变成‘O’，如果和边界上的点联系不到一起，那么就是'X'
  41.     row = board.size(), col = board[0].size();
  42.     int dummy_node = row * col + 10;
  43.     init(dummy_node + 5);
  44.     for (int i = 0; i < row; i++) {
  45.         for (int j = 0; j < col; j++) {
  46.             if (board[i][j] == 'O') {
  47.                 if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
  48.                     merge(node(i, j), dummy_node);
  49.                 } else {
  50.                     for (int k = 0; k < 4; k++) {
  51.                         int nx = i + dx[k], ny = j + dy[k];
  52.                         if (check(nx, ny) && board[nx][ny] == 'O') {
  53.                             merge(node(i, j), node(nx, ny));
  54.                         }
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.     }
  61.     // 检查是否和dummy_node是一组的，如果是就变成'O',否则变成'X'
  62.     for (int i = 0; i < row; i++) {
  63.         for (int j = 0; j < col; j++) {
  64.             if (find(node(i, j)) == find(dummy_node)) {
  65.                 board[i][j] = 'O';
  66.             } else {
  67.                 board[i][j] = 'X';
  68.             }
  69.         }
  70.     }
  71. }

}; ```