Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня,…
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня, одиноко стоящего на шахматной доске. На всякий случай напомним, что конь ходит буквой «Г» — на две клетки по горизонтали или вертикали в любом направлении, и потом на одну клетку в направлении, перпендикулярном первоначальному. Исходные данные В первой строке находится единственное число N, 1 ≤ N ≤ 64 — количество тестов. В каждой из последующих N строк содержится очередной тест: два символа (маленькая латинская буква от 'a' до 'h' и цифра от 1 до 8) — стандартное шахматное обозначение клетки, на которой стоит конь. При этом буква обозначает вертикаль, а цифра — горизонталь. Результат Выведите N строк: в каждой из них должно находиться единственное число — количество клеток шахматной доски, находящихся под боем коня. Реши на питоне
Задача состоит в подсчёте числа допустимых ходов коня с заданной клетки на стандартной 8x8 доске.
Ключевые идеи:
- Координаты клетки: файлы a..h соответствуют x=0..7, ранги 1..8 – y=0..7.
- Ходы коня: 8 вариантов (dx, dy): (1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2).
- Подсчитываем, сколько из них попадают в диапазон 0..7 по обеим координатам.
Алгоритм:
- Считываем N и далее N клеток (например, "a1", "e4").
- Для каждой клетки переводим в координаты (x,y).
- Подсчитываем число допустимых ходов, проверяя 0 <= x+dx < 8 и 0 <= y+dy < 8.
- Выводим результат по строкам.
Пример кода на Python:
import sys
def count_knight_moves(square: str) -> int:
# Переводим клетку в координаты 0..7
file = ord(square[0]) - ord('a') # 'a' -> 0, ..., 'h' -> 7
rank = int(square[1]) - 1 # '1' -> 0, ..., '8' -> 7
moves = [
(1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2)
]
cnt = 0
for dx, dy in moves:
x = file + dx
y = rank + dy
if 0 <= x < 8 and 0 <= y < 8:
cnt += 1
return cnt
def main():
data = sys.stdin.read().strip().split()
if not data:
return
t = int(data[0])
res = []
for i in range(1, t + 1):
sq = data[i]
res.append(str(count_knight_moves(sq)))
print("\n".join(res))
if __name__ == "__main__":
main()
Пояснения по сложности:
- Время: для каждого теста выполняется ровно 8 проверок, так что итоговая сложность O(N).
- Память: константная дополнительная память.
Некоторые справочные значения для intuition:
- Конь в углу (например, a1) имеет 2 возможных хода.
- Конь на краю, но не в углу (например, a2) имеет 3 хода.
- В центре доски (например, d4) — 8 ходов.
