0051.cpp (1186B)
1 class Solution { 2 vector<vector<string>> res; 3 vector<string> board; 4 unordered_set<int> used; 5 int n; 6 7 bool valid(int row, int col) { return row >= 0 && row < n && col >= 0 && col < n; } 8 9 bool safe(int row, int col) { 10 static vector<pair<int, int>> ofsts = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; 11 12 if (used.count(col)) return false; 13 for (auto &ofst : ofsts) { 14 int a = row + ofst.first, b = col + ofst.second; 15 while (valid(a, b)) { 16 if (board[a][b] == 'Q') return false; 17 a += ofst.first, b += ofst.second; 18 } 19 } 20 return true; 21 } 22 23 void rec(int row) { 24 if (row == n) { 25 res.push_back(board); 26 return; 27 } 28 29 for (int i = 0; i < n; i++) { 30 if (!safe(row, i)) continue; 31 used.insert(i); 32 board[row][i] = 'Q'; 33 rec(row + 1); 34 used.erase(i); 35 board[row][i] = '.'; 36 } 37 } 38 39 public: 40 vector<vector<string>> solveNQueens(int n) { 41 this->n = n; 42 board = vector<string>(n, string(n, '.')); 43 rec(0); 44 return res; 45 } 46 };