print1463. Бег по коридору

printБег по коридору

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и `N` пикселей по горизонтали. Каждый пиксель определяется координатами `(a,\ b)`, где `a` – номер строки от 1 до 2, а `b` – номер столбца от 1 до `N`.
На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр – "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).
В начале у игрока нулевой уровень усталости. Каждое перемещение добавляет к текущему уровню усталости единицу. Как только игрок перемещается на пиксель, занятый эликсиром, он выпивает эликсир, и уровень усталости уменьшается на единицу. Таким образом, перемещение на пиксель с эликсиром не увеличивает уровня усталости. Когда игрок покидает клетку, на которой был эликсир, она становится свободной.
Изначально игрок находится в пикселе с координатами `(1,\ 1)`. Цель игры – добраться до `N`-ого столбца, минимизировав конечный уровень усталости.
Вам необходимо написать программу, которая по заданному плану коридора определит минимальный уровень усталости, с которым можно пройти игру.
Формат входного файла
В первой строке входного файла содержится число `N` – горизонтальное разрешение дисплея. Далее следует описание игрового поля – пара строк длиной `N` каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) – занятому препятствием, символ "X" (прописная латинская X) – пикселю с эликсиром.
Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".
Гарантируется, что можно добраться до `N`-ого столбца.
Формат выходного файла
В выходной файл выведите единственное число – минимальный уровень усталости, которого можно достичь, пройдя игру.
Ограничения
2 ≤ N ≤ 100

Пример ввода 1

2
..
.#

Пример вывода 1

1

Пример ввода 2

6
....X.
#XXX..

Пример вывода 2

3
Источник: Весенний турнир ДВГУ, 2009
loading