R. Карта сокровищ

На пиратской карте отмечено N точек, в которых зарыты сокровища. Каждая точка задана координатами (xi​, yi​). Координаты указаны в километрах. Команда Капитана Крюка хочет составить маршрут, чтобы собрать как можно больше кладов. Однако есть ограничение: для любых двух соседних точек маршрута (xi​, yi​) и (xj​, yj​) координаты xi​ и xj​ могут различаться только последней цифрой, как и координаты yi​ и yj​ тоже могут различаться только последней цифрой. Например, после точки (15, 10) они могут отправиться в точку (18, 16), а вот из точки (14, 68) в точку (19, 71) пройти уже не получится, ведь 68 и 71 различаются не только последней цифрой. Из точки (5, 12) в точку (13, 14) попасть тоже нельзя, так как числа 5 и 13 отличаются в разряде десятков. По заданным координатам определите, какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк.

Формат ввода

В первой строке указано число N (1≤N≤105) — количество точек, отмеченных на карте сокровищ. В следующих N строках содержатся пары координат: xi​ и yi​ — координаты i-ой точки. Координаты — целые числа не меньше нуля и не больше 109. Гарантируется, что совпадающих точек в списке нет.

По состоянию на 4 сентября 2024 года в третьем тесте обнаружены повторяющиеся точки в квадрате-победителе.

Формат вывода:

Выведите одно число — максимальное количество точек, которое Капитан Крюк сможет посетить по маршруту, построенному по описанным правилам.

Пример

Ввод

9
10 18
17 15
25 21
0 21
1 16
25 29
24 24
8 26
10 20

Вывод

3

Решение

Из-за специфической постановки, задача кажется сложнее, чем есть на самом деле.
Может показаться, что капитан может ходить только по вертикали и горизонтали, как в ладья в шахматах, но в реальности, он может ходить как заблагорассудится в пределах одного квадрата 10×10 ячеек. Таким образом задача сводится к тому, чтобы найти квадрат с максимальным количеством “сокровищ” и вывести это количество в качестве ответа.
После того, как задача переформулирована, единственная сложность – правильно подобрать формат ключа для словаря, чтобы корректно и удобно накапливать количество сокровищ в квадрате. За основу можно взять координаты точки деленные нацело на 10. Таким образом все точки имеющие одинаковые старшие разряды автоматически будут попадать в один квадрат.

treasures = dict()

for _ in range(count := int(input())):
    x, y = input().split()
    index = (int(x) // 10, int(y) // 10)
    treasures[index] = treasures.get(index, 0) + 1

print(max(treasures.values()))