Задача
Эрик работает охранником в университете, поэтому после рабочего дня он обходит здание и выключает свет на ночь.
В здании n этажей и две лестницы слева и справа. На каждом этаже есть m комнат вдоль коридора, который соединяет левую и правую лестницы. Другими словами, здание можно представить как прямоугольник из n строк и m + 2 столбцов, где первый и последний столбец — лестницы, а m столбцов посередине — комнаты.
Эрик сейчас стоит на первом этаже на левой лестнице. Он хочет выключить везде свет, при этом, он не хочет подниматься на этаж выше до того, как выключит весь свет на текущем этаже. Конечно, Эрик должен побывать в комнате, чтобы выключить в ней свет. Эрик тратит одну минуту на то, чтобы подняться по лестнице на один этаж или перейти в соседнюю команату/на лестницу из соседней комнаты или с лестницы на том же этаже. Выключение света в комнате, в которой Эрик находится, не отнимает у него времени.
Помогите Эрику найти минимальное время для выключения всего света в здании.
Заметьте, что Эрик не должен возвращаться на исходную позицию, а также то, что он не обязан посещать комнаты, в которых свет и так выключен.
Входные данные:
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — количество этажей и количество комнат на каждом этаже, соответственно.
Следующие n строк содержат описание здания. Каждая строка содержит строку из нулей и единиц длины m + 2, описывающую один этаж (левую лестницу, затем m комнат, затем правую лестницу), где 0 означает, что свет выключен, а 1 означает, что свет включен. Этажи даны в порядке сверху вниз, в частности, последняя строка описывает первый этаж.
Первые и последние символы каждой строки описывают лестницы, поэтому они всегда равны 0.
Выходные данные:
Выведите одно число — минимально возможное время, необходимое для того, чтобы выключить весь свет.
Примеры:
| Входные данные |
Выходные данные |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Пояснения:
В первом примере Эрик сначала пойдет в комнату 1 на первом этаже, а затем — в комнату 2 на втором этаже, используя любую лестницу.
Во втором примере он пойдет сначала в четвертую комнату на первом этаже, поднимется на один этаж по правой лестнице, зайдет в четвертую комнату на втором этаже, опять поднимется по правой лестнице, пойдет во вторую комнату на последнем этаже.