Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

С++ ПРОШУ Помогите пожалуйста

Leyla Nuriyeva Ученик (193), открыт 4 недели назад
Дано число N . Определите, сколькими способами на доске N × N можно расставить N ферзей, не бьющих друг друга.
Входные данные

5
Результат работы

10
1 ответ
SemyonK Мастер (1180) 4 недели назад
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Проверка, можно ли безопасно поставить ферзя в текущую строку и столбец
bool isSafe(const vector<int>& queens, int row, int col) {
for (int r = 0; r < row; ++r) {
int c = queens[r];
if (c == col || abs(c - col) == abs(row - r)) {
return false;
}
}
return true;
}

// Рекурсивная функция для поиска всех решений
void solveNQueens(int n, int row, vector<int>& queens, int& solutions) {
if (row == n) {
solutions++;
return;
}
for (int col = 0; col < n; ++col) {
if (isSafe(queens, row, col)) {
queens[row] = col;
solveNQueens(n, row + 1, queens, solutions);
queens[row] = -1; // сброс для возврата назад (backtracking)
}
}
}

int main() {
int n;
cout << "Введите размер доски (N): ";
cin >> n;

vector<int> queens(n, -1); // Вектор для хранения позиции ферзей в каждой строке
int solutions = 0; // Счетчик решений

solveNQueens(n, 0, queens, solutions);

cout << "Количество способов расстановки " << n << " ферзей: " << solutions << endl;

return 0;
}
Leyla NuriyevaУченик (193) 3 недели назад
СПАСИБО!!!!!!!!!!!!
Похожие вопросы