diff options
Diffstat (limited to 'introductory_problems/chessboard_and_queens.cpp')
-rw-r--r-- | introductory_problems/chessboard_and_queens.cpp | 55 |
1 files changed, 55 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); +} |