Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ilyasoloma
0 / 0 / 0
Регистрация: 27.09.2015
Сообщений: 16
#1

Задача "Ладья в Лабиринте" - C++

14.10.2015, 10:52. Просмотров 795. Ответов 10
Метки нет (Все метки)

Ладья – это шахматная фигура, которая за один ход может переместиться на любое количество клеток по горизонтали или вертикали. При этом она не может «перепрыгивать» через стоящие на ее пути фигуры.

Вася недавно соорудил на шахматной доске своеобразный лабиринт, поставив в некоторые клетки доски пешки (самые «слабые» шахматные фигуры). Теперь он хочет знать, за какое минимальное количество ходов ладья может добраться из одной клетки в другую, перемещаясь по свободным клеткам доски.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа: n и m (1 ≤ n, m ≤ 500) – размеры лабиринта.

Каждая из последующих n строк содержит m символов. j-ый символ i-ой из этих строк соответствует клетке с координатами (i, j). Он равен «.» (точка), если клетка пуста, «P», если занята пешкой, «S», если это начальная клетка для ладьи, и «F», если это конечная клетка.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество ходов, требуемое ладье для того, чтобы из начальной клетки попасть в конечную. Если конечная клетка недостижима из начальной выведите -1.

Примеры

1 тест:
вход:
4 4
F.PS
.PP.
.PP.
....
выход: 3
2 тест:
вход:
4 4
F.PS
.PP.
.PP.
.P..
выход: -1

Была идея вводить 2 массива, один на горизонталь, другой на вертикаль, но реализовать не смог. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2015, 10:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача "Ладья в Лабиринте" (C++):

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Программа "Робот в лабиринте" - C++
программа на тему "Робот в лабирине".Программа должна отображать очертания лабиринта и робота и позволять управлять движением робота по...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...

10
pav1uxa
1843 / 1695 / 642
Регистрация: 23.01.2014
Сообщений: 6,072
Завершенные тесты: 1
14.10.2015, 19:52 #2
ilyasoloma, Могу сказать что задача на теорию графов. Пока их не изучите - будет не очень просто ее решить
1
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
14.10.2015, 20:10 #3
pav1uxa, при чём тут теория графов? Ну то есть её тоже можно за уши притянуть сюда, но гораздо проще и удобнее не грузить себе мозг теорией, а реализовать какой-нибудь из изначально известных алгоритмов "поиска пути".
Поиск пути это ну настолько задроченная всеми задача, что реализовать её можно(и нужно), не задумываясь особо о графах как таковых.
Гуглим алгоритмы А-стар, волновой, Дейстры и.т.д. и радуемся.
https://www.google.com/search?q=А-стар
https://www.google.com/search?q=волновой+алгоритм
0
Fulcrum_013
Нарушитель
698 / 762 / 74
Регистрация: 14.12.2014
Сообщений: 6,034
Завершенные тесты: 3
14.10.2015, 20:17 #4
Цитата Сообщение от ilyasoloma Посмотреть сообщение
. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
Задача на модификацию алгоритм Дейкстры поиска пути. Работает аналогично закраске с затравкой. Начинаете с текущего положения ладьи, запишите в него 0. запишите во все соседние клетки в которые возможен ход 1 и направление. В их соседей в которые ход возможен без изменения направления тоже 1 в остальные в которые возможен - 2, если там нет 1. и так дальше прибавляя 1 при изменении направления пока не дойдете до конечной точки. Число в конечной точке и будет количеством ходов.

Добавлено через 4 минуты
[/
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов?
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных.
Абсолютно естественно что теория графов тут вообще ни при делах .
1
pav1uxa
1843 / 1695 / 642
Регистрация: 23.01.2014
Сообщений: 6,072
Завершенные тесты: 1
14.10.2015, 20:57 #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов? Ну то есть её тоже можно за уши притянуть сюда, но гораздо проще и удобнее не грузить себе мозг теорией,
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Гуглим алгоритмы А-стар, волновой, Дейстры и.т.д. и радуемся.
Ну давайте погуглим:
Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе.
Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Как Вы думаете, человек, который даже не представляет что такое граф, ребро, вершина и так далее, легко разберется в этих алгоритмах? Это все равно что учиться читать не зная букв.
1
Dimension
Dimension
557 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
14.10.2015, 21:56 #6
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов?
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
волновой, Дейстры
эти алгоритмы на графах используются
0
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
14.10.2015, 23:47 #7
Ой-ой, ну всё! заклевали...
Только вот одно слово вы пропускаете мимо глаз. Теория графов, теория! А алгоритмы поиска пути и тем более их реализация на С++ это уже практика.
И не надо смешивать. Следуя вашим советам, человек пойдёт читать толстый томик высшей математики и никогда к нам не вернётся.
А я ему сказал погуглить конкретные примеры алгоритмов, с названиями, программы для которых на С++ давно написаны.
И ему не следует заморачиваться даже о внутреннем устройстве этих программ, что уж тем более говорить о математических выкладках за ними?

Добавлено через 5 минут
Цитата Сообщение от pav1uxa Посмотреть сообщение
Как Вы думаете, человек, который даже не представляет что такое граф, ребро, вершина и так далее, легко разберется в этих алгоритмах?
легко
google+название алгоритма+copy+paste
а по вашим советам он заснёт на учебнике математики, перечитывая очередной раз определение 100500го термина
граф, ребро, вершина ....ориентированно связный полный двудольный k-хроматический гиперграф.
Очень нужный термин.
0
Fulcrum_013
Нарушитель
698 / 762 / 74
Регистрация: 14.12.2014
Сообщений: 6,034
Завершенные тесты: 3
15.10.2015, 00:14 #8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Очень нужный термин.
Пока не осилит понятие древовидный граф алгоритм неосилит
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
легко google+название алгоритма+copy+paste
Легко превратится в быдлокодера. Если не въехал алгоритм Дейкстры и остальные на нем основанные тут в чистом виде не пойдут, их модифицировать надо.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а по вашим советам он заснёт на учебнике математики,
Программист - это в первую очередь математик. Знаешь сколько раза пытаясь заснуть на учебнике/cправочнике по математике просыпался лежа головой на клавиатуре?
0
ilyasoloma
0 / 0 / 0
Регистрация: 27.09.2015
Сообщений: 16
15.10.2015, 10:05  [ТС] #9
Сегодня ещё раз вернулся к ней, решил, что рациональным решением будут ввод двумерного массива и обработка его волновым алгоритмом. Днях попытаюсь сделать
0
Lensato
49 / 49 / 24
Регистрация: 07.10.2015
Сообщений: 170
11.11.2015, 17:59 #10
ilyasoloma, если вы решили эту задачу, то я бы хотел сравнить со своим решением.
Мой вариант (приложил) быстро решает таблицы до 400х400.
Там конечно небольшой бардак и плохая оптимизация, но мне интересна ваша идея.
Лучше сразу оптимизировать более качественный алгоритм.
0
Вложения
Тип файла: zip rook.zip (9.0 Кб, 10 просмотров)
_sitizen_
0 / 0 / 0
Регистрация: 27.04.2014
Сообщений: 4
25.12.2016, 23:19 #11
В данном случае оптимальным будем волновой метод поиска кратчайшего пути с распространением действия волны не только к соседним (от очередной ячейки элементам), а к краю свободной области.

PS посмотрите здесь: Ладья в лабиринте есть решение
всем кто будет кидать в меня камни: достали уже быдлокодеры, которые лишь указывают, куда нужно идти и что учить, хотя иногда, даже изучив теорию графов, иногда на мелочах тормозишь и не можешь сразу придумать решение, а ведь все что нужно - указать способ...
0
25.12.2016, 23:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2016, 23:19
Привет! Вот еще темы с ответами:

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...


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

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

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