24/04/2024 14:54:23

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1493. Подземелье

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

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

Напишите программу, которая определит по плану подземелья минимальное время до встречи.

Первая строка ввода содержит два целых числа `N` и `M` – размеры подземелья (`2\ ≤\ N,\ M\ ≤\ 100`), далее следует `N` строк, содержащих по `M` символов '.' или ‘#’ – план подземелья. Символом '.' обозначается проход, а символом '#' – стена. В начальной позиции первый спелеолог находится в левом верхнем углу, а второй – в правом верхнем углу подземелья. Верхние углы подземелья свободны от препятствий. За одну единицу времени спелеолог может перейти в соседнюю клетку по вертикали или горизонтали.

Вывести одно целое число – минимальное время до встречи спелеологов в подземелье. Если встреча не может состояться, вывести число `-1`.

Пример ввода

4 7
.#####.
.#...#.
...#.#.
####...

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

02/10/2010	Личное первенство Южного Урала (C)
09/12/2010	Сборы: Общий итог (4B)
30/12/2010	Сборы 4: Практика (B)
04/07/2022	Лето 2022-4 (D)