51. N 皇后

class Solution {
  // This should be spoken as `vector<vector<array<char, n>>>`.
  vector<vector<string>> Result_;
  vector<int> Col_, Diag_, Back_;
  vector<string> Path_;

  void DFS(int R, int N) {
    if (R == N) {
      Result_.push_back(Path_);
      return;
    }

    // Iterate over the column.
    for (int C = 0; C < N; ++C) {
      // If the col/diag/back is marked, skip.
      if (Col_[C] || Diag_[N + C - R] || Back_[C + R])
        continue;

      // Generate string of this row.
      string Current_(N, '.');
      Current_[C] = 'Q';

      // Mark col, diag, and backs; then move to next row.
      Col_[C] = Diag_[N + C - R] = Back_[C + R] = 1;
      Path_.push_back(Current_);
      DFS(R + 1, N);
      Path_.pop_back();
      Col_[C] = Diag_[N + C - R] = Back_[C + R] = 0;
    }
  }

public:
  vector<vector<string>> solveNQueens(int n) {
    Col_.resize(n);
    // To avoid negative indices, we have to make their size twice of n.
    Diag_.resize(2 * n);
    Back_.resize(2 * n);

    DFS(0, n);
    return Result_;
  }
};