Теперь давайте посмотрим на местность с высоты — словно вы летите на самолёте.
Перед вами — прямоугольная таблица с высотами.
Внутри этой сетки тоже могут встречаться «горы» — точки, которые выше всех своих соседей по 8 направлениям.
Создайте функцию find_mountains(data), которая принимает список списков чисел и возвращает кортеж пар номеров всех гор.
Нумерация начинается с 1 (по строкам и столбцам).
Края таблицы считаются окружёнными горами бесконечной высоты, поэтому в них гор быть не может.
Примечание
Ваше решение должно содержать только функции.
Пример
Ввод
result = find_mountains([
[1, 1, 1],
[1, 2, 1],
[1, 1, 1]
])Вывод
result = ((2, 2),)Ввод
result = find_mountains([
[1, 1, 1, 1, 1, 1],
[1, 2, 1, 5, 4, 1],
[1, 1, 1, 3, 4, 3],
[2, 3, 3, 1, 2, 3],
[1, 2, 1, 3, 2, 1]
])Вывод
result = ((2, 2), (2, 4))Решение
Представлено два решения: Одно по подсказке Яндекса, второе – интуитивное. И это тот случай, когда интуитивное лучше, потому что проще.
Первое решение – по подсказке. Мы разбиваем квадрат на квадратики 3×3 и проверяем, что центр выше окраин.
Второе решение просто пробегает по всем точкам и сравнивает их с соседями
Глядя на оба решения, возникает мысль, а не стоит ли нам улучшить читабельность обоих решений и не добавить ли проверку на наличие по соседству пиков? Ведь искать пик рядом с уже найденым бессмысленно. Это реализовано в третьем решении, основанном на втором.
Посмотреть код
Решение
from itertools import product
def find_mountains(data):
if not data or len(data) < 3 or not data[0] or len(data[0]) < 3:
return ()
rows = len(data)
cols = len(data[0])
mountain_positions = []
for row, col in product(range(1, rows - 1), range(1, cols - 1)):
current_height = data[row][col]
if all(current_height > data[neighbor_row][neighbor_col]
for neighbor_row, neighbor_col in product(range(row - 1, row + 2), range(col - 1, col + 2))
if (neighbor_row, neighbor_col) != (row, col)):
mountain_positions.append((row + 1, col + 1))
return tuple(mountain_positions)Решение
def find_mountains(data):
if not data or len(data) < 3 or not data[0] or len(data[0]) < 3:
return ()
rows = len(data)
cols = len(data[0])
mountain_positions = []
for row in range(1, rows - 1):
for col in range(1, cols - 1):
current_height = data[row][col]
is_mountain = True
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
if (dr, dc) != (0, 0):
if current_height <= data[row + dr][col + dc]:
is_mountain = False
break
if not is_mountain:
break
if is_mountain:
mountain_positions.append((row + 1, col + 1))
return tuple(mountain_positions)Решение
def find_mountains(data):
if not data or len(data) < 3 or not data[0] or len(data[0]) < 3:
return ()
rows = len(data)
cols = len(data[0])
mountain_positions = []
skip_points = set()
def is_mountain(row, col, height):
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
if (dr, dc) != (0, 0):
if height <= data[row + dr][col + dc]:
return False
return True
for row in range(1, rows - 1):
for col in range(1, cols - 1):
if (row, col) not in skip_points:
height = data[row][col]
if is_mountain(row, col, height):
mountain_positions.append((row + 1, col + 1))
skip_points.update(
(row + dr, col + dc)
for dr in [-1, 0, 1]
for dc in [-1, 0, 1]
if (dr, dc) != (0, 0)
)
return tuple(mountain_positions)