LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 与边界相连的 O 标记为 #，其他的 O修改为 X，最后把 # 恢复为 O 即可

class Solution {
 public:
  void solve(vector<vector<char>>& board) {
    if (empty(board) || empty(board[0])) {
      return;
    }
    int m = size(board);
    int n = size(board[0]);
    for (int i = 0; i < m; ++i) {  // 上下两边
      dfs(board, i, 0);
      dfs(board, i, n - 1);
    }
    for (int i = 0; i < n; ++i) {  // 左右两边
      dfs(board, 0, i);
      dfs(board, m - 1, i);
    }
    for (auto& x : board) {
      for (auto& y : x) {
        if (y == 'O') {
          y = 'X';
        } else if (y == '#') {
          y = 'O';
        }
      }
    }
  }

  void dfs(vector<vector<char>>& board, int i, int j) {
    if (board[i][j] == 'O') {
      board[i][j] = '#';
      if (i > 0) {
        dfs(board, i - 1, j);
      }
      if (i + 1 < size(board)) {
        dfs(board, i + 1, j);
      }
      if (j > 0) {
        dfs(board, i, j - 1);
      }
      if (j + 1 < size(board[0])) {
        dfs(board, i, j + 1);
      }
    }
  }
};