Рассмотрим прямоугольное поле, состоящее из w×h квадратных клеток. В клетке A стоит фишка. За один ход можно подвинуть фишку в любую соседнюю по стороне клетку. Сколько ходов потребуется, чтобы добраться до клетки B? Важное дополнение: края поля склеены по принципу проективной плоскости. А именно, i-я сверху клетка левого края — соседняя с i-й снизу клеткой правого края, а j-я слева клетка верхнего края — соседняя с j-й справа клеткой нижнего края (для всех i и j, для которых существуют эти клет

Для решения задачи можно использовать алгоритм поиска в ширину (BFS).

1. Создадим очередь и добавим в нее стартовую клетку А.
2. Создадим двумерный массив visited размером w×h и заполним его значениями False, чтобы отметить все клетки, которые мы уже посетили.
3. Инициализируем переменную steps значением 0, чтобы отслеживать количество сделанных шагов.
4. Пока очередь не пуста, будем извлекать элемент из очереди:
– Увеличиваем переменную steps на 1.
– Проверяем, является ли текущая клетка равной клетке B. Если это так, то возвращаем значение steps, так как мы достигли цели.
– Помечаем текущую клетку как посещенную.
– Для каждой соседней клетки в верхнем, нижнем, левом и правом направлениях:
– Если соседняя клетка не посещена и не является стеной:
– Добавляем ее в очередь.
5. Если мы не нашли клетку B, возвращаем -1, так как пути до нее не существует.

Этот алгоритм работает на основе итераций в ширину от стартовой клетки A и продолжает искать клетку B, покуда не пройдет по всем возможным путям или пока не будет достигнута цель.

Оценка сложности алгоритма BFS составляет O(w×h), где w и h – ширина и высота поля соответственно.