На бесконечной координатной сетке муравей стартует из (1000, 1000) и ходит на одну клетку по четырём направлениям. Клетки, где сумма цифр координат X и Y больше 25, недоступны. Сколько клеток он может посетить, включая начальную? Напишите решение на Python 2.

Муравей может посетить 148 848 клеток. Нужно обойти связанную со стартом область с помощью BFS/DFS, а не просто посчитать все клетки с допустимой суммой цифр.

Прямые x=999, x=1999, y=999, y=1999 непроходимы: сумма цифр одной такой координаты уже больше 25. Поэтому область конечна, несмотря на бесконечность сетки.

# Python 2
from collections import deque

def digits(n):
    return sum(int(c) for c in str(abs(n)))

seen = set([(1000, 1000)])
queue = deque([(1000, 1000)])
while queue:
    x, y = queue.popleft()
    for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
        if (nx, ny) not in seen and digits(nx) + digits(ny) <= 25:
            seen.add((nx, ny))
            queue.append((nx, ny))
print(len(seen))  # 148848

Обход хранит только достижимые клетки. Внутри ограниченного квадрата стоимость обработки клетки постоянна, итоговые время и память линейны по размеру посещённой области.