Ферапонт, внимательно слушавший спор Силантия с Фалалеем, решил свою лепту внести. Спросил, какие исследования уже проведены по грантам.

Фалалей рад был тему разговора сменить. Начал рассказывать, что серьёзные разработки по теории игр имеются. В частности, по антагонистическим играм. Да про такие вещи, конечно, на примере лучше рассказать.

Есть клеточное поле, некоторые его клетки считаются запрещёнными. Есть два игрока — для простоты и определённости назовем их Заяц и Волк. Изначально они находятся в разных (не запрещённых) клетках. Игроки ходят по очереди. Игрок может перемещаться из текущей клетки только в клетку, граничащую с текущей по стороне и не являющуюся запрещённой.

Первым ходит Заяц. Заяц может сделать ход в любом направлении или же остаться на месте.

Волк всегда делает ход по кратчайшему пути к текущему положению Зайца. При прочих равных направление движения Волк выбирает в следующем порядке: «влево», «вверх», «вправо», «вниз». Если путь от Волка до Зайца не существует, Волк остаётся на месте.

Волк одерживает победу, если после очередного хода он оказывается в клетке с Зайцем. Заяц одерживает победу, если он продержался k ходов и ещё не пойман.

Ваша задача — сделать как можно больше ходов за Зайца.