andewK

Untitled

Feb 17th, 2021
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <iostream>
  3. #include <vector> ;
  4.  
  5. using namespace std;
  6.  
  7.  
  8. vector<pair<int, int>> array;
  9.  
  10. int a(int n, int k) {
  11.     if (k == n) { // если вдруг прошли уже всю доску то очевидно доступна 1 позиция
  12.         return 1;
  13.     }
  14.     int sum = 0;
  15.     for (int i = 0; i < n; i++) { // перебираем все колонки
  16.         bool is_attacking = false;
  17.         for (int j = 0; j < array.size(); j++) { // перебираем всех уже заполненых ферзей
  18.             if (array[j].first == i || abs(array[j].first - i) == abs(array[j].second - k)) {
  19.                 is_attacking = true; // текущую позицию уже ктото атакует
  20.                 break;
  21.             }
  22.         }
  23.         if (!is_attacking) { // если никто не атакует
  24.             array.push_back({i, k}); // занимем эту позицию ферзём
  25.             sum += a(n, k + 1); // находим сколько возможных позиций ещё есть
  26.             array.pop_back(); // удаляем этого ферзя
  27.         }
  28.     }
  29.     return sum; // возвращаем количество позиций
  30. }
  31.  
  32. int main()
  33. {
  34.     int n;
  35.     cin >> n;
  36.     cout << a(n, 0);
  37.  
  38.     return 0;
  39. }
  40.  
RAW Paste Data