Advertisement
he_obviously

Untitled

Sep 21st, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <set>
  5. #include <map>
  6. #include <vector>
  7. #include <limits.h>
  8. /*
  9. #include <ext/rope>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. */
  13.  
  14. using namespace std;
  15. /*
  16. using namespace __gnu_pbds;
  17. */
  18.  
  19. /*
  20. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
  21. */
  22.  
  23. const int N = 8;
  24. int cnt = 0;
  25. bool printed = 0;
  26. char a[N][N];
  27. vector<pair<int, int>> pos;
  28. vector<char> type;
  29. vector<pair<pair<int, int>, pair<int, int>>> ans;
  30. vector<bool> used;
  31.  
  32. bool reachable(int i, int j) {
  33.     int i1 = pos[i].first, j1 = pos[i].second,
  34.         i2 = pos[j].first, j2 = pos[j].second;
  35.     if (type[i] == 'R') {
  36.         return (i2 == i1 || j2 == j1);
  37.     }
  38.     else if (type[i] == 'B') {
  39.         return (abs(i1 - i2) == abs(j1 - j2));
  40.     }
  41.     else if (type[i] == 'Q') {
  42.         return (i1 == i2 || j1 == j2) ||
  43.             (abs(i1 - i2) == abs(j1 - j2));
  44.     }
  45.     else {
  46.         return (abs(i1 - i2) * abs(j1 - j2) == 2);
  47.     }
  48. }
  49.  
  50. void print() {
  51.     for (auto x : ans) {
  52.         auto f = x.first, s = x.second;
  53.         cout << (char)('a' + f.second) << N - f.first << ":" << (char)('a' + s.second) << N - s.first << "\n";
  54.     }
  55. }
  56.  
  57. void gen(int k = 1) {
  58.     if (printed) {
  59.         return;
  60.     }
  61.     else if (k == cnt) {
  62.         print();
  63.         printed = 1;
  64.         return;
  65.     }
  66.     else {
  67.         for (int i = 0; i < cnt; ++i) {
  68.             if (!used[i]) {
  69.                 for (int j = 0; j < cnt; ++j) {
  70.                     if (j != i && !used[j]) {
  71.                         if (reachable(i, j)) {
  72.                             ans.push_back({ pos[i], pos[j] });
  73.                             auto p = pos[i];
  74.                             pos[i] = pos[j];
  75.                             used[j] = 1;
  76.                             gen(k + 1);
  77.                             ans.pop_back();
  78.                             used[j] = 0;
  79.                             pos[i] = p;
  80.                         }
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.     }
  86. }
  87.  
  88. int main() {
  89.  
  90.     ios::sync_with_stdio(0);
  91.     cin.tie(0); cout.tie(0);
  92.  
  93.     for (int i = 0; i < N; ++i) {
  94.         for (int j = 0; j < N; ++j) {
  95.             cin >> a[i][j];
  96.             if (a[i][j] != '.') {
  97.                 type.push_back(a[i][j]);
  98.                 pos.push_back({ i, j });
  99.                 cnt += 1;
  100.             }
  101.         }
  102.     }
  103.  
  104.     used.resize(cnt, false);
  105.  
  106.     gen();
  107.  
  108.     if (!printed) {
  109.         cout << "NO SOLUTION";
  110.     }
  111.  
  112.     return 0;
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement