Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Ферзь, ладья и конь

(Время: 1 сек. Память: 16 Мб Сложность: 34%)

Для решения данной задачи нужно понять, каким образом определить: бьет ли та или иная фигура, находящаяся в клетке (x1,y1) некоторую клетку (x2,y2). При этом следует помнить, что нас интересуют только пустые клетки, т.к. именно их и нужно считать. Задача сильно упрощается тем, что фигуры могут "ходить" сквозь друг друга, поэтому проверяя возможность достижения фигурой некоторой клетки, можно принебрегать другими фигурами.

Проще всего эта задача решается для ладьи, т.к. некоторая клетка будет находиться под боем тогда и только тогда, когда одна из координат у рассматриваемых клеток совпадает, т.е. x1=x2 или y1=y2 (клетки расположены либо на одной горизонтали, либо на одной вертикали).

В случае с ферзем, помимо ограничений на ладью (ферзь может двигаться как и ладья) добавляется условие расположения на одной из диагоналей, математически это произоисходит только тогда, когда модули разностей координат этих клеток совпадают, т.е. |x1-x2|=|y1-y2| (для слона это условие является единственным).

Случай с конем, пожалуй, самый сложный. Конечно, можно проверить все 8 клеток, в которые может сходить конь из клетки (x1,y1) и если окажется, что одной из таковых является клетка (x2,y2), то клетка "под боем", иначе - нет. Но запись в условии 8ми проверок достаточно громоздка и поэтому возможны ошибки. Данный вопрос можно решить более хитро: из того, что конь ходит буквой "Г" следует, что модуль произведения разностей координат этих двух клеток всегда равен двум. С другой стороны, это так же является достаточным условием. Поэтому возможность достижения конем клетки математически эквивалентна выполнению условия |(x1-x2)*(y1-y2)|=2.

Наиболее простой способ подсчета количества клеток "под боем" заключается в переборе всевозможных клеток и проверки их на достижимость одной из трех фигур. Это позволит избежать повторений клеток, которые бьют несколько фигур одновременно. Следует при этом не забывать, что клетки, на которых стоят фигуры не должны учитываться.


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483