Статья Автор: Лебедев Дмитрий

TUZ_5-09 Количество безопасных полей на шахматной доске со слонами

TUZ_5-09 Количество безопасных полей на шахматной доске со слонами

TUZ_5-09 Количество безопасных полей на шахматной доске со слонами
5.9. Количество безопасных полей на шахматной доске со слонами
Дано: шахматная доска n×n с несколькими слонами на ней, где горизонтали и вертикали
пронумерованы от 0 до n – 1. Слоны могут двигаться только по диагонали.
Слоны могут атаковать фигуры, стоящие на одной с ними диагонали.
Напишите функцию, которая в качестве входных данных принимает размер шахматной доски, 
координаты слонов в виде списка кортежей и возвращает количество безопасных полей.
В табл. 5.9 показаны ожидаемые результаты для некоторых входных данных.
Таблица 5.9. Некоторые ожидаемые результаты для задачи определения безопасных полей на шахматной доске со слонами
n, bishops Ожидаемый результат
10
(2, 3), (4,4)
68
91
(1,1), (4,4), (3, 5), (0, 7)
8002
20
(1,0), (3,6), (11, 5), (1, 2)
307
7
(0,2), (3,9), (3, 4)
29

Алгоритм
Алгоритм принимает размер шахматной доски n и список bishops координат слонов на доске.
Он вычисляет количество безопасных полей на доске, то есть количество полей,
которые не заняты слонами или не находятся под угрозой атаки со стороны слона.
Алгоритм сначала инициализирует переменную safe_squares значением 0,
которая затем будет использоваться для подсчета количества безопасных полей.
Далее он создает два множества: diagonal1 и diagonal2 – для хранения полей на каждой диагонали,
находящейся под угрозой атаки.
Для каждого слона на доске алгоритм вычисляет индексы полей на двух диагоналях,
где расставлены слоны, и добавляет их в соответствующие множества diagonal1 и diagonal2.
Наконец, алгоритм перебирает все поля на доске и проверяет, занято ли каждое поле слоном
на той же диагонали или находится под угрозой.
Если поле не занято и не находится под угрозой атаки слоном,
то количество безопасных полей увеличивается на 1.
На выходе алгоритм возвращает количество безопасных полей.


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать