Задача . D. Змейка

Напомним правила одной очень популярной игры, которая называется «Змейка» (эта игра также известна как «Удав», «Питон» или «Червяк»).

Игровое поле представляет собой прямоугольную таблицу размера n × m. Некоторые клетки поля считаются непроходимыми (стены), все остальные клетки поля проходимы.

Вы управляете змейкой, которая состоит из сегментов. Каждый сегмент занимает ровно одну проходимую клетку поля, причем в любой проходимой клетке находится не более одного сегмента. Все сегменты пронумерованы целыми числами от 1 до k, где k — длина змейки. Сегмент с номером 1 называется головой, а с номером k — хвостом. Для любого i (1 ≤ i < k) клетки поля, в которых находятся сегменты с номерами i и i + 1, являются соседними, то есть имеют общую сторону.

В одной из проходимых клеток поля находится яблоко. Цель змейки — достичь яблока и съесть его (то есть сделать так, чтобы голова оказалась в той же клетке, где и яблоко).

В процессе игры змейка двигается. За один ход змейка может переместить голову в одну из соседних клеток поля. При этом все остальные сегменты подтягиваются за головой. То есть каждый сегмент с номером i (1 < i ≤ k) перемещается в клетку, где только что находился сегмент с номером i - 1. Считайте, что перемещение всех сегментов, включая голову, происходит одновременно (смотри второй тестовый пример). Если после хода голова змейки оказывается в непроходимой клетке или в клетке, в которой находится другой сегмент, то змейка умирает. Поэтому такие ходы мы будем считать недопустимыми.

Ваша задача — определить наименьшее количество допустимых ходов, необходимых для того, чтобы змейка достигла яблока.