Участникам соревнования по бегу по пересечённой местности необходимо преодолеть маршрут из левого верхнего угла в правый нижний угол участка, состоящего из 8 × 8 клеток. Участник может перемещаться из клетки в одну из четырёх клеток, имеющих общую сторону с клеткой, где он находится в данный момент, не выходя при этом за границу квадрата.

Участникам соревнования по бегу по пересечённой местности необходимо преодолеть маршрут из левого верхнего угла в правый нижний угол участка, состоящего из 8 × 8 клеток. Участник может перемещаться из клетки в одну из четырёх клеток, имеющих общую сторону с клеткой, где он находится в данный момент, не выходя при этом за границу квадрата. На рисунке изображён вид участка и один из возможных маршрутов бегуна. Участники всегда выбирают кратчайший маршрут.

Организаторы соревнований хотят удлинить маршрут спортсменов, для этого они планируют перекрыть некоторые клетки препятствиями, чтобы они стали недоступны для участников. Организаторы хотят разместить препятствия так, чтобы кратчайший маршрут от старта до финиша стал как можно длиннее. Также они хотят использовать минимально возможное число препятствий.

Помогите организаторам — разместите препятствия нужным образом, отметив соответствующие квадраты на рисунке ниже. Чем длиннее будет кратчайший путь от старта до финиша в вашем ответе, тем больше баллов вы получите. При одинаковой длине кратчайшего пути больше баллов получит ответ, содержащий меньшее число препятствий. При этом, независимо от количества препятствий, решение с большей длиной пути получит больше баллов, чем с меньшей.