leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0052.cpp (1125B)

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