1 class Solution { 2 public: 3     vector<vector<string>> solveNQueens(int n) { 4         vector<vector<string>> result; 5         vector<int> pos(n, -1); 6         vector<int> isColumnSafe(n, 1); 7         vector<int> isDiag1Safe(2 * n - 1, 1); // 主对角线 8         vector<int> isDiag2Safe(2 * n - 1, 1); // 斜对角线 9         checkPos(result, pos, isColumnSafe, isDiag1Safe, isDiag2Safe, 0, n);10         return result;11     }12 private:13     void checkPos(14                 vector<vector<string>>& result,15                 vector<int>& pos,16                 vector<int>& isColumnSafe,17                 vector<int>& isDiag1Safe,18                 vector<int>& isDiag2Safe,19                 int i,20                 int n21                 )22     {23         for (int j = 0; j < n; ++j) {24             bool flag = isColumnSafe[j] && isDiag1Safe[i - j + n - 1] && isDiag2Safe[i + j];25             if (flag) {26                 isColumnSafe[j] = 0;27                 isDiag1Safe[i - j + n - 1] = 0;28                 isDiag2Safe[i + j] = 0;29                 pos[i] = j;30                 if (i == n - 1) {31                     vector<string> vec(n, string(n, ‘.‘));32                     int cnt = 0;33                     for (int k = 0; k < n; ++k) {34                         vec[cnt ++][pos[k]] = ‘Q‘;35                     }36                     result.push_back(vec);37                 }38                 else {39                     checkPos(result, pos, isColumnSafe, isDiag1Safe, isDiag2Safe, i + 1, n);40                 }41                 isColumnSafe[j] = 1;42                 isDiag1Safe[i - j + n - 1] = 1;43                 isDiag2Safe[i + j] = 1;44             }45         }46     }47 };