leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0052.cpp (1125B)

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