Имеется поле 10×10. У каждой клетки есть координата (x, y), где x — номер строки на поле, y — номер столбца на поле. Левая верхняя клетка имеет координаты (1, 1).
Изначально в клетке с координатами (3, 7) находятся 120 шаров. Но есть нюанс: в каждой клетке может находиться максимум один шар, поэтому запускается алгоритм балансировки шаров.
Данный алгоритм выглядит следующим образом:
- Рассматриваем клетки в любом порядке. Если в текущей клетке шаров больше, чем 1, то мы начинаем избавляться от лишних шаров по очереди. Причём действует правило: пока шар не нашёл пустую клетку или не удалился, другие шары не могут начинать перемещение.
- За один шаг шар может переместиться в любую из 4-х соседних по ребру клеток. Если на поле есть пустая клетка, шар будет стремиться в неё попасть.
- Шар может временно встать в клетку, где уже есть шары, чтобы продолжить дальше свой путь, но никакой шар, покинувший стартовую клетку, не может снова на неё вступить.
- Если на очередном шаге шар нашёл пустую клетку — он остаётся там (шар нашёл свою клетку). Клетка считается пустой, если в ней нет ни одного шара.
- Если у шара нет возможности найти пустую клетку, то он доходит до любой угловой клетки (исходные угловые клетки и любые другие угловые клетки) и удаляется вместе с ней. Это значит, что данная угловая клетка навсегда пропадает с поля, и шары, которые были в ней, соответственно тоже пропадают. Угловой считается клетка, у которой две смежные стороны не граничат с другими клетками.
Алгоритм балансировки заканчивается, когда на поле не будет ни одной клетки, в которой находится больше 1 шара.
Определите, сколько шаров на поле останется после выполнения алгоритма балансировки.