Задача о восьми ферзях
Задача. На шахматной доске 8х8 произвольным образом расставлено 8 ферзей, по одному на каждой вертикали, других фигур на доске нет. Ферзь может ходить на любое количество клеток как по диагонали, так и по вертикали или горизонтали, но при этом не может перепрыгивать через другие фигуры. Необходимо добиться такой позиции, в которой ни один ферзь не находится под боем любого другого, и сделать это за минимальное количество ходов.
Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.
Выходные данные. Одна строка, содержащая последовательность соответствующих минимальных количеств ходов без пробелов.
Тесты
| Входные данные | Выходные данные | Комментарий |
| 2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5 | 71 | пройден |
Решение
«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).
Для вычисления правильных расстановок вызывается рекурсивная функция line_up (параметром которого является номер столбца). Внутри функции line_up вызывается функция check (параметр — номер столбца), она проверяет горизонтальную линию и две диагонали на поля, которые бьет ферзь. Элементам массива правильных расстановок присваиваются номера горизонтальных линий (алгоритм «Поиск с возвратом»).
Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <stdio.h> #include<fstream> using namespace std; const int n = 8;// Размер поля int count_test = 0;// Количество тестов int mincountstep = n + 1; //Количество ходов int frtest[n]; //расстановка теста int fr[n]; //правильная расстановка bool check(int nf) // проверка битых полей { if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей for (int i = 0; i < n && fr[i] >= 0; i++) { if ( i == nf ) continue; if (fr[nf] == fr[i] ) return false; // (Горизонталь) if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ } return true; //если поле свободно } void calc_min_strok() // Вычисление количества ходов и нахождение минимального { int countstep = 0; // количество ходов for (int i = 0; i < n; i++){ if ( frtest[i] != fr[i] ) countstep++; } if ( mincountstep > countstep ) mincountstep = countstep; } bool line_up(int i) //рекурсивня функция установки ферзей (стек расстановок) { if ( i > n-1) return false ; for (int j = 0; j < n; j++) { fr[i] = j; if ( check(i) == true ) { if ( i == n-1) { //Если дошли до последней колонки и всё хорошо calc_min_strok(); } else { line_up(i+1); } } fr[i] = -1 ; } return false ; } int main() { cin >> count_test; //Обнуление начального массива for (int test = 0; test < count_test; test++ ){ mincountstep = n + 1; for (int i = 0; i < n; i++) fr[i] = -1; //ввод данных теста for (int i = 0; i < n; i++) { cin >> frtest[i]; frtest[i]--; } line_up(0); cout << mincountstep; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import java.util.*; import java.lang.*; import java.io.*; public class Main { static int n ;// Размер поля static int count_test ;// Количество тестов static int mincountstep ; //Количество ходов static int frtest[]; //расстановка теста static int fr[]; //правильная расстановка static boolean check(int nf) // проверка битых полей { if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей for (int i = 0; i < n && fr[i] >= 0; i++) { if ( i == nf ) continue; if (fr[nf] == fr[i] ) return false; // (Горизонталь) if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ } return true; //если поле свободно } static void calc_min_strok() // Вычисление количества ходов и нахождение минимального { int countstep = 0; // количество ходов for (int i = 0; i < n; i++){ if ( frtest[i] != fr[i] ) countstep++; } if ( mincountstep > countstep ) mincountstep = countstep; } static boolean line_up(int i) //рекурсивная функция установки ферзей (стек расстановок) { if ( i > n-1) return false ; for (int j = 0; j < n; j++) { fr[i] = j; if ( check(i) == true ) { if ( i == n-1) { //Если дошли до последней колонки и всё хорошо calc_min_strok(); } else { line_up(i+1); } } fr[i] = -1 ; } return false ; } public static void main(String[] args) { Scanner in = new Scanner(System.in); count_test = in.nextInt(); n = 8;// Размер поля mincountstep = n + 1; //Количество ходов frtest = new int [n]; //расстановка теста fr = new int [n]; //правильная расстановка //Обнуление начального массива for (int test = 0; test < count_test; test++ ){ mincountstep = n + 1; for (int i = 0; i < n; i++) fr[i] = -1; //ввод данных теста for (int i = 0; i < n; i++) { frtest[i] = in.nextInt(); frtest[i]--; } line_up(0); System.out.print(mincountstep); } System.out.println(); } } |
Забыли в конце вывести пустую строку.
Без этого на e-olimp.com задача не пройдет.
Зачтено.
Не вижу ссылок на успешное прохождение, поэтому только 5 баллов.