UniLecs #133. Pac-Man
UniLecsЗадача: смоделируем нашу версию игры Pac-Man. Pac-Man играет на прямоугольном поле N*M, где двигается слева направо, потом спускается на след.строку и идет справа налево, и так до самого конца. За каждый свой ход он съедает по одной точке. Необходимо определить, сколько точек сьел Pac-Man в точке (x, y) игрового поля (включая саму точку), где x - строка, а y - столбец.
Входные данные: N, M - размеры игрового поля от 1 до 10^6. (X, Y) - координаты искомой точки на поле.
Вывод: кол-во съеденных точек в точке (X, Y)
Пример: N = M = 3, (X, Y) = (2,1)
* * *
* * *
* * *
Answer: 6
Идея: по сути нам нужно формировать матрицу сьеденных точек Пакманом, где элемент (i,j) - кол-во сьеденных точек Пакманом. Основная сложность задачи заключается в правильном заполнении строк матрицы, каждую из которых нужно заполнять либо слева направо, либо наооборот. Для этого будем использовать отдельную переменную, ктр будет отвечать за направление движение по строке direction: значение 1 - идем слева направо, -1 - идем справа налево. То есть дойдя до конца строки Пакману нужно перейти на новую строку, при этом оставшись в этом же столбце. На каждой итерации проверям дошли ли мы до искомой точки или нет.
Детали реализации смотрите в коде.
Реализация:
https://gist.github.com/unilecs/1596bd2aea0b12edab9e1dfd1997068a
Test: