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

• 回溯法

class Solution {
 public:
  vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> v(n, string(n, '.'));
    dfs(res, v, n, 0);
    return res;
  }

  void dfs(vector<vector<string>>& res, vector<string>& v, int n, int row) {
    if (n == row) {
      res.emplace_back(v);
      return;
    }
    for (int col = 0; col < size(v[0]); ++col) {
      if (isValid(v, row, col)) {
        v[row][col] = 'Q';        // 该位置有效则放置棋子
        dfs(res, v, n, row + 1);  // 继续考虑下一行
        v[row][col] = '.';  // 回溯，该位置不放置棋子，继续考虑当前行的下一列
      }
    }
  }

  bool isValid(const vector<string>& v, int row, int col) {
    // 上方
    for (auto& x : v) {
      if (x[col] == 'Q') {
        return false;
      }
    }
    // 左上
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
      if (v[i][j] == 'Q') {
        return false;
      }
    }
    // 右上
    for (int i = row - 1, j = col + 1; i >= 0 && j < size(v[0]); --i, ++j) {
      if (v[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }
};