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