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. 如何改变方向：

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

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

    q.push({next_x, next_y});

// 进入队列之后，立即改变标号，这样可以避免重复进入队列的问题
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; } }

int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (x != y) {
        if (r[x] <= r[y]) {
            fa[x] = y;
        } else {
            fa[y] = x;
        }

        if (r[x] == r[y]) {
            r[y] += 1;
        }
    }
}

// 2维坐标到1维数字
int node(int i, int j) {
    return i * col + j;
}

bool check(int i, int j) {
    if (0 <= i && i <= row - 1 && 0 <= j && j <= col - 1) {
        return true;
    }

    return false;
}

void solve(vector<vector<char>>& board) {
    // 并查集，3个步骤
    // 1. 对于所有位于边界上的点，和特殊点放到一起
    // 2. 对于所有内部的点，和上下左右可以连通的点放到一起
    // 3. 如果内部和边界联系上了，也就是和“特殊点”在一起，那么，就变成‘O’，如果和边界上的点联系不到一起，那么就是'X'
    row = board.size(), col = board[0].size();
    int dummy_node = row * col + 10;
    init(dummy_node + 5);
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (board[i][j] == 'O') {
                if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                    merge(node(i, j), dummy_node);
                } else {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k], ny = j + dy[k];
                        if (check(nx, ny) && board[nx][ny] == 'O') {
                            merge(node(i, j), node(nx, ny));
                        }
                    }
                }
            }
        }
    }

    // 检查是否和dummy_node是一组的，如果是就变成'O',否则变成'X'
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (find(node(i, j)) == find(dummy_node)) {
                board[i][j] = 'O';
            } else {
                board[i][j] = 'X';
            }
        }
    }
}

}; ```