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

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

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

TUZ_5-08_ Количество безопасных полей на шахматной доске с ладьями
5.8. Количество безопасных полей на шахматной доске с ладьями
Ладья – это шахматная фигура, и позиция каждой ладьи представлена парой (горизонталь, вертикаль),
где горизонтали и вертикали пронумерованы от 0 до n – 1. Ладьи могут атаковать фигуры,
стоящие на одной с ними горизонтали или вертикали.
Цель этой задачи – определить набор безопасных полей на шахматной доске,
где ни одна ладья не сможет атаковать их.
Напишите функцию, которая принимает размер шахматной доски, координаты ладей в виде списка кортежей 
и возвращает количество безопас ных полей.
В табл. 5.8 показаны ожидаемые результаты для некоторых входных данных.
Таблица 5.8. Некоторые ожидаемые результаты для задачи определения безопасных полей на шахматной доске с ладьями n, rooks Ожидаемый результат 
n, rooks Ожидаемый результат 
10
(2, 3), (4, 4)		 64
91
(1,1), (4,4), (3, 5), (0, 7)		 7569
20
(1,1), (4,4), (3, 5), (0, 7) 		 272
7
(0,2), (3,9), (3, 4)		 20

Алгоритм
Пусть rooks – список ладей, а n – размер шахматной доски.
Для каждого i в rooks алгоритм сохраняет
  •  i[0] в массиве Unsaferow и 
  • i[1] в масси- ве Unsafecol.
На следующем шаге он получает количество безопасных горизонталей и вертикалей как
safedrow = n – len(set(Unsaferow)) и safecol = n – len(set (Unsafecol)) соответственно.
На последнем шаге подсчитывается число безопасных полей как safedrow * safecol.

В листинге 5.8 приводится код на Python, вычисляющий количество безопасн ых полей на шахматной доске.
Листинг 5.8. Определение количества безопасных полей на шахматной доске с ладьями
1 def Safe_Squares_Rooks_of_Chessboard(n, rooks):
2     Unsafe_squares_in_rows = []
3     Unsafe_squares_in_columns = []
4     for i in rooks:
5         Unsafe_squares_in_rows.append(i[0])
6         Unsafe_squares_in_columns.append(i[1])
7     # Чтобы исключить повторяющиеся числа, используется множество
8     safed_rows = n - len(set(Unsafe_squares_in_rows))
9     # Чтобы исключить повторяющиеся числа, используется множество
10     safed_columns = n - len(set(Unsafe_squares_in_columns))
11     # Получить количество безопасных полей
12     safe = safed_rows * safed_columns
13     return safe


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