Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1463. Бег по коридору
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание (10B) |
| 14/07/2010 | Лето 2010 - 10 (B) |
| 19/11/2010 | Занятие 10 (F) |
| 09/12/2010 | Сборы: Общий итог (6C) |
| 13/01/2011 | Сборы 6: Практика (C) |
| 13/01/2011 | Сборы 6: Домашнее задание (A) |
| 11/02/2013 | Занятие 16 (F) |
| 02/12/2015 | Занятие по теме "Разбиение на подзадачи, динамическое программирование" (C) |
| 04/07/2018 | Лето 2018 - 5 (C) |
| 08/07/2020 | Лето 2020 - 4 (C) |
| 06/07/2022 | Лето 2022-5 (D) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
