Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <map>
- #include <vector>
- #include <limits.h>
- /*
- #include <ext/rope>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- */
- using namespace std;
- /*
- using namespace __gnu_pbds;
- */
- /*
- #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
- */
- const int N = 8;
- int cnt = 0;
- bool printed = 0;
- char a[N][N];
- vector<pair<int, int>> pos;
- vector<char> type;
- vector<pair<pair<int, int>, pair<int, int>>> ans;
- vector<bool> used;
- bool reachable(int i, int j) {
- int i1 = pos[i].first, j1 = pos[i].second,
- i2 = pos[j].first, j2 = pos[j].second;
- if (type[i] == 'R') {
- return (i2 == i1 || j2 == j1);
- }
- else if (type[i] == 'B') {
- return (abs(i1 - i2) == abs(j1 - j2));
- }
- else if (type[i] == 'Q') {
- return (i1 == i2 || j1 == j2) ||
- (abs(i1 - i2) == abs(j1 - j2));
- }
- else {
- return (abs(i1 - i2) * abs(j1 - j2) == 2);
- }
- }
- void print() {
- for (auto x : ans) {
- auto f = x.first, s = x.second;
- cout << (char)('a' + f.second) << N - f.first << ":" << (char)('a' + s.second) << N - s.first << "\n";
- }
- }
- void gen(int k = 1) {
- if (printed) {
- return;
- }
- else if (k == cnt) {
- print();
- printed = 1;
- return;
- }
- else {
- for (int i = 0; i < cnt; ++i) {
- if (!used[i]) {
- for (int j = 0; j < cnt; ++j) {
- if (j != i && !used[j]) {
- if (reachable(i, j)) {
- ans.push_back({ pos[i], pos[j] });
- auto p = pos[i];
- pos[i] = pos[j];
- used[j] = 1;
- gen(k + 1);
- ans.pop_back();
- used[j] = 0;
- pos[i] = p;
- }
- }
- }
- }
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- for (int i = 0; i < N; ++i) {
- for (int j = 0; j < N; ++j) {
- cin >> a[i][j];
- if (a[i][j] != '.') {
- type.push_back(a[i][j]);
- pos.push_back({ i, j });
- cnt += 1;
- }
- }
- }
- used.resize(cnt, false);
- gen();
- if (!printed) {
- cout << "NO SOLUTION";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement