Автор задачи и разработчик: Владислав Власов
Заметим, что нам нужно найти кратчайший путь в некотором графе, где ребро может весить $$$1$$$ или $$$0$$$. Для решения таких задач подойдет алгоритм Дейкстры или $$$0$$$-$$$1$$$ bfs.
Теперь поймем, что в каждой клетке может быть выгодно быть в разные моменты, а не только в минимальный возможный. Но при этом если два момента времени $$$t_1$$$ и $$$t_2$$$ отличаются на время, кратное восьми, то достаточно знать $$$\min(t_1, t_2)$$$, так как каждые $$$8$$$ единиц времени все стрелки возвращаются в исходное положение. Таким образом, вместо обычного $$$\mathtt{dist}[v]$$$, минимального времени, в которое можно оказаться в вершине $$$v$$$, будем хранить восемь массивов $$$\mathtt{dist}_d[v]$$$ — минимальное время, в которое можно оказаться в вершине $$$v$$$, имеющее остаток $$$d$$$ по модулю $$$8$$$.
Пересчет же будет таким же, как и в обычном поиске в ширину, только теперь каждую вершину можно воспринимать как $$$8$$$ независимых вершин: $$$(v, d)$$$ будет соответствовать вершине $$$v$$$, в которую мы попали в момент времени $$$t$$$, что $$$t \bmod 8 = d$$$. Время работы алгоритма равно $$$\mathcal{O}(n + m)$$$, но с в $$$8$$$ раз большей константой.