eolymp

Пятерка за неделю 2

Конь и пешка против коня
   Для решения данной задачи особых алгоритмов не нужно, однако мы хотим остановиться на анализе одного из подходов к решению данной задачи, так как он помогает найти ключ ко всему классу подобных шахматных задач.
   Необходимо помнить, что привычное для шахматиста обозначение поля для расположения белого коня c4, впрочем, как и для остальных шахматных фигур с точки зрения программиста «неправильно», так как первым должно идти наименование (номер) строки, а вторым – номер столбика. Преобразование литерного значения номера столбца в числовое - особой сложности не представляет. 
   При анализе допустимых ходов шахматных фигур именно конь является наиболее неудобной фигурой, так как если он находится близко к краю доски, то возникают небольшие проблемы, связанные с проверкой «выскакивания» коня за пределы доски.
   Обойти этот момент можно кардинальным способом: рассматривать не обычную доску 8х8, а расширенную на 2 горизонтали и вертикали во все стороны, то есть доску 12х12. В этом случае удобно объявлять массив pole размером [-1..10,-1..10] и разрешить коню ходить по правилам его хода даже за пределы доски. Обозначим расположение белых фигур, например, числом 1, а черных -1. В этом случае белый конь сможет  ходить как на свободные поля (у которых значение 0), так и на поля, где находятся фигуры противника. В случае если соответствующее значение массива меньше или равно нуля – ход разрешен. Занесем во все разрешенные клетки значение 2, а потом на обычном поле 8х8 посчитаем количество двоек.
   Конечно, существует и более оптимальный алгоритм решения конкретно именно этой задачи, но именно с методологической точки зрения рекомендуется применять описанный выше подход. В этом случае при решении подобных задач затруднений не возникнет.

Слон и пешка против слона

   Данная задача является логическим продолжением следующей, но в отличие от предыдущей, нам нужно рассматривать массив не 12х12, а 10х10. Т.е. мы можем нарастить на одну горизонталь или вертикаль стандартную шахматную доску, чтобы уменьшить количество проверок выхода за пределы доски, а при подсчете опять использовать только «внутреннюю» стандартную доску 8х8.

   При проверке позиций необходимо учесть следующие критические моменты:

   - белой пешке некуда ходить;
   - белая пешка может побить слона противника;
   - белый слон может побить слона противника и при этом уже не может ходить на клетки, расположенные на диагонали за ним;
   - белый король не может ходить под шах;
   - белый слон или белая пешка не могут ходить, так своим ходом они откроют шах от слона противника.

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

Максимальное количество фигур

   Задача является чисто математической и базируется на свойствах ходов упомянутых в задаче фигур, и симметрии шахматной доски. Пусть доска имеет размеры M x N.

   Ладья простреливает все вертикали и горизонтали, поэтому максимально мы можем поставить min(M,N).

   Учитывая, что ферзь ходит и как ладья, максимальное количество ферзей на доске равно максимальному количеству ладей.

   Конь при своем ходе ходит на клетку противоположного цвета, поэтому максимальное количество коней на доске равно ((M*N)+1) div 2.

   Попробуйте нарисовать несколько небольших досок, расставить на них королей и вывести самостоятельно похожую формулу для максимального количества королей.