Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
2 / 2 / 0
Регистрация: 24.01.2019
Сообщений: 8
1

Найти путь в переулке

03.09.2019, 18:56. Показов 1072. Ответов 3
Метки нет (Все метки)

Помогите с задачей:

Росс и Рейчел купили в квартиру отвратительно длинный диван. Росс работает палеонтологом в Нью-Йоркском Музее Естественной Истории, поэтому с его зарплатой он решил не тратиться на доставку. Росс посчитал, что сможет сам донести диван до своей квартиры.
По пути до своего дома Росс попал в переулок, который из-за своей странной структуры напо- минал скорее лабиринт, чем Нью-Йоркский переулок.
Переулок представляет собой поле n на m клеток. Каждая клетка либо пуста, либо в ней нахо- дится препятствие. В том магазине, в котором были Росс и Рейчел, диваны бывают разной длины, но все они занимают k подряд идущих клеток в одной линии для некоторого k. Разумеется, диван не может находиться в клетке, в которой находится препятствие. Росс очень сильный, поэтому он может перенести диван любой длины.
Изначально, Росс может зайти в переулок в любой клетке левого столбца, но он должен держать диван параллельно левой границе переулка. Чтобы выйти из переулка, он должен оказаться в какой- нибудь клетке правого столбца переулка, держа диван параллельно этой границе.
Когда Росс держит диван параллельно одной из границ переулка, он может перенести его на одну клетку вдоль этой границы, или же он может взять диван за один из его концов, поднять его в этом месте в воздух, и опустить его параллельно другой стороне переулка. Разумеется, он может сделать эти действия, только если после этих действий диван будет находится на пустых клетках.
Теперь Россу и Рейчел интересно, какой максимальной длины диван можно перенести через переулок.

Входные данные:
В первой строке входных данных находятся два целых числа n и m (1 􏰀<= n, m 􏰀 <= 300) — количество строк и столбцов в переулке, соответственно. В следующих n строках находятся m символов. j-й символ i-й строки равняется «#», если в j-й клетке i-й строки находится стена, иначе он равен «.».

Выходные данные:
В единственной строке выведете одно число — максимальное количество клеток, которое может занимать диван такой, что Росс может перенести его через переулок. Если диван никакой длины нельзя пронести через переулок, выведите число 0.

Стандартный ввод
3 5
...##
.#.#.
##...
Стандартный вывод:
2
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.09.2019, 18:56
Ответы с готовыми решениями:

Системе не удается найти указанный путь. И путь к рабочему столу :С
Подскажите в чем может быть проблема - Открываю ранее деланный проект - и выводит сообщение, что не...

Найти путь
Проверьте решение, пожалуйста. Два автомобиля ехали в одном направлении. Первый ехал равномерно со...

Найти путь к картинке.
Подскажите, как получить путь к картинке, по которой произведен щелчок? Добавлено через 4 часа...

Найти кратчайший путь
Добрый день, знаю таких программ куча и т.д., но найти подходящую я не смог. Может у кого имеется в...

3
34 / 22 / 7
Регистрация: 23.12.2018
Сообщений: 101
04.09.2019, 15:56 2
Ищи в интернете, тыщу раз уже эту задачку решали.
0
2 / 2 / 0
Регистрация: 24.01.2019
Сообщений: 8
04.09.2019, 17:41  [ТС] 3
Можете подсказать где она есть. Я и так долго искал
0
0 / 0 / 0
Регистрация: 08.01.2017
Сообщений: 4
05.09.2019, 21:04 4
Добрый вечер, хотел бы поинтересоваться итогом, смогли решить задачу?

Добавлено через 47 секунд
Скиньте ссылки на эту задачу, будьте любезны
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.09.2019, 21:04

Найти путь к файлу
ОБХОД ГРАФА В ШИРИНУ Задание: Требуется найти путь к файлу, указанному в первой строке входного...

Найти свой путь
Здравствуйте, дорогие. У меня есть проблема: я не знаю в какую сферу программирования идти. Все...

Найти кратчайший путь
Всем привет, кто может, помогите: Дан двумерный массив, нужно найти кратчайший путь от левого...

Найти путь к библиотеке
Ребят,привет. Первый раз с linux работаю,подскажите. Установил на Ubuntu 16 пакет библиотеки...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.