summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-05 13:17:11 -0700
committerJack Sangdahl <[email protected]>2025-03-05 13:17:11 -0700
commit4ff18ecb768e4636e0c63af33ae7acb2cad7edc6 (patch)
treef5f405f3aa94c03e36a3a3e9a2fec1d0300a19ae
parent1bd17a77301438997ccc4e3eaf7ebe04474a5767 (diff)
downloadcses-4ff18ecb768e4636e0c63af33ae7acb2cad7edc6.tar.gz
cses-4ff18ecb768e4636e0c63af33ae7acb2cad7edc6.zip
1624. chessboard and queens
-rw-r--r--introductory_problems/chessboard_and_queens.cpp55
-rw-r--r--introductory_problems/readme.md7
2 files changed, 62 insertions, 0 deletions
diff --git a/introductory_problems/chessboard_and_queens.cpp b/introductory_problems/chessboard_and_queens.cpp
new file mode 100644
index 0000000..4dc5f2f
--- /dev/null
+++ b/introductory_problems/chessboard_and_queens.cpp
@@ -0,0 +1,55 @@
+// 1624. Chessboard and Queens
+#include <bits/stdc++.h>
+#include <cstdio>
+using namespace std;
+
+const int n = 8;
+char c;
+int ans;
+bool b[n][n], input[n][n];
+
+bool place(int x, int y) {
+ bool valid = true;
+ for (int i = 0; i < n; i++)
+ if (b[x][i] || b[i][y])
+ valid = false;
+ for (int i = 0; x - i >= 0 && y + i < n; i++)
+ if (b[x - i][y - i])
+ valid = false;
+ for (int i = 0; x - i >= 0 && y + i < n; i++)
+ if (b[x - i][y + i])
+ valid = false;
+ return valid;
+}
+
+bool check(void) {
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < n; j++)
+ if (b[i][j] && input[i][j])
+ return false;
+ return true;
+}
+
+void dfs(int i) {
+ if (i == n) {
+ if (check())
+ ans++;
+ return;
+ }
+ for (int j = 0; j < n; j++)
+ if (place(i, j)) {
+ b[i][j] = true;
+ dfs(i + 1);
+ b[i][j] = false;
+ }
+}
+
+int main() {
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < n; j++) {
+ scanf(" %c", &c);
+ input[i][j] = (c == '*');
+ }
+ dfs(0);
+ printf("%d\n", ans);
+}
diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md
index 32519e6..52fbe2d 100644
--- a/introductory_problems/readme.md
+++ b/introductory_problems/readme.md
@@ -119,3 +119,10 @@ There are `n` apples with known weights. Your task is to divide the apples into
**Input**: The first input line has an integer `n`: the number of apples. The next input line has `n` integers `p1, p2, ..., pn`: the weight of each apple. (Example: 5`\n`3 2 7 4 1)
**Output**: Print one integer: the minimum difference between the weights of the groups. (Example: 1)
+
+### Chessboard and Queens
+Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking eachother. How many possible ays are there to place the queens?
+
+**Input**: The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).
+
+**Output**: Print one integer: the number of ways you can place the queens.