Задача 102925
|
Название задачи: Испытание шаха . |
 |
Условие
Известна легенда, что в древней Лимонии любой претендент на должность визиря при шахе должен был выдержать следующее испытание. Ему дается доска размером 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 получается сразу.
