ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102925
Тема:    [ Перебор с отсечениями ]
Сложность: 3
Классы:
Название задачи: Испытание шаха .
В корзину
Прислать комментарий

Условие

Известна легенда, что в древней Лимонии любой претендент на должность визиря при шахе должен был выдержать следующее испытание. Ему дается доска размером M × M и некоторое количество шахматных фигур: ферзей, ладей, слонов, коней и королей. Претендент должен расставить их на доске таким образом, чтобы ни одна из фигур не била другие фигуры, и все фигуры были выставлены на доске. Если претендент выдерживал испытание, он назначался визирем, а если не выдерживал... то не назначался. Напишите программу, которая будет решать эту головоломку.

Входные данные

Первое число во входном файле задает размер доски M (2 ≤ M ≤ 12). Следующие 5 целых неотрицательных чисел K, Q, R, B, N задают соответственно количество королей, ферзей, ладей, слонов и коней, которые требуется расставить. Общее количество фигур не превосходит M2 . Фигуры подобраны так, что искомая расстановка существует.

Выходные данные

Вывести в выходной файл доску с расставленными фигурами в виде M строк по M символов в каждой. Пустые поля обозначаются символом . (точка), поля с королями – K, ферзями – Q, ладьями – R, слонами – B, конями – N.

Пример входного файла

4 0 0 4 0 0

Пример выходного файла

R...
..R.
...R
.R..

Решение

Эта задача решается аналогично задаче расстановки N ферзей на доске N × N, но при решении следует учесть некоторые нюансы. Поскольку чем больше «небитых» полей, тем больше перебираемых вариантов для расстановки очередной из фигур, логично первыми расставлять те фигуры, которые бьют много полей. Следовательно, порядок их выставления на доску должен быть примерно таким: ферзи, ладьи, слоны, кони, короли. 

В процессе перебора необходимо определять, какие из полей находятся под боем. Причем набор таких полей меняется каждый раз, когда мы добавляем или удаляем фигуру. Для быстрой проверки, является ли поле «небитым», следует для каждого поля хранить число бьющих его фигур. 

Для улучшения работы алгоритма можно перебирать поля доски не подряд (первая строка слева направо, вторая строка, ...), а в каком-нибудь другом порядке. Например, для расстановки коней можно перебирать сначала все поля черного цвета, а затем все поля белого цвета. При такой организации перебора расстановка 72 коней на доске 12 × 12 получается сразу.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 2
Название Перебор с возвратом
гЮДЮВЮ
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .