leetcode

commit 4394fc6e1ed9d57e852cfbad3a2fa33156a811c6
parent 5c3b5ef77af21a5637ebd6aa2d2997dc72ebca24
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 22 Mar 2023 22:38:21 +0100

Random Problems

Diffstat:
A
Problems/0051.cpp
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
Problems/0052.cpp
 | 
52
++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 107 insertions(+), 0 deletions(-)
diff --git a/Problems/0051.cpp b/Problems/0051.cpp
@@ -0,0 +1,53 @@
+class Solution {
+  vector<vector<string>> res;
+  vector<string> board;
+  unordered_set<int> used;
+  int n;
+
+  bool valid(int row, int col) {
+    return row >= 0 && row < n && col >= 0 && col < n;
+  }
+
+  bool safe(int row, int col) {
+    static vector<pair<int, int>> ofsts = {
+        { 1,  1},
+        { 1, -1},
+        {-1,  1},
+        {-1, -1}
+    };
+
+    if (used.count(col)) return false;
+    for (auto &ofst : ofsts) {
+      int a = row + ofst.first, b = col + ofst.second;
+      while (valid(a, b)) {
+        if (board[a][b] == 'Q') return false;
+        a += ofst.first, b += ofst.second;
+      }
+    }
+    return true;
+  }
+
+  void rec(int row) {
+    if (row == n) {
+      res.push_back(board);
+      return;
+    }
+
+    for (int i = 0; i < n; i++) {
+      if (!safe(row, i)) continue;
+      used.insert(i);
+      board[row][i] = 'Q';
+      rec(row + 1);
+      used.erase(i);
+      board[row][i] = '.';
+    }
+  }
+
+public:
+  vector<vector<string>> solveNQueens(int n) {
+    this->n = n;
+    board = vector<string>(n, string(n, '.'));
+    rec(0);
+    return res;
+  }
+};
diff --git a/Problems/0052.cpp b/Problems/0052.cpp
@@ -0,0 +1,52 @@
+class Solution {
+  vector<string> board;
+  unordered_set<int> used;
+  int n, res;
+
+  bool valid(int row, int col) {
+    return row >= 0 && row < n && col >= 0 && col < n;
+  }
+
+  bool safe(int row, int col) {
+    static vector<pair<int, int>> ofsts = {
+        { 1,  1},
+        { 1, -1},
+        {-1,  1},
+        {-1, -1}
+    };
+
+    if (used.count(col)) return false;
+    for (auto &ofst : ofsts) {
+      int a = row + ofst.first, b = col + ofst.second;
+      while (valid(a, b)) {
+        if (board[a][b] == 'Q') return false;
+        a += ofst.first, b += ofst.second;
+      }
+    }
+    return true;
+  }
+
+  void rec(int row) {
+    if (row == n) {
+      res++;
+      return;
+    }
+
+    for (int i = 0; i < n; i++) {
+      if (!safe(row, i)) continue;
+      used.insert(i);
+      board[row][i] = 'Q';
+      rec(row + 1);
+      used.erase(i);
+      board[row][i] = '.';
+    }
+  }
+
+public:
+  int totalNQueens(int n) {
+    this->n = n;
+    board = vector<string>(n, string(n, '.'));
+    rec(0);
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -66,6 +66,8 @@ for solving problems.
 |  0048  |   Medium   | [Rotate Image](Problems/0048.cpp)                                                                |
 |  0049  |   Medium   | [Group Anagrams](Problems/0049.cpp)                                                              |
 |  0050  |   Medium   | [Pow(x, n)](Problems/0050.cpp)                                                                   |
+|  0051  |    Hard    | [N-Queens](Problems/0051.cpp)                                                                    |
+|  0052  |    Hard    | [N-Queens II](Problems/0052.cpp)                                                                 |
 |  0053  |   Medium   | [Maximum Subarray](Problems/0053.cpp)                                                            |
 |  0054  |   Medium   | [Spiral Matrix](Problems/0054.cpp)                                                               |
 |  0055  |   Medium   | [Jump Game](Problems/0055.cpp)                                                                   |