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

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

Восстановить пароль Регистрация
 
ilyasoloma
0 / 0 / 0
Регистрация: 27.09.2015
Сообщений: 12
14.10.2015, 10:52     Задача "Ладья в Лабиринте" #1
Ладья – это шахматная фигура, которая за один ход может переместиться на любое количество клеток по горизонтали или вертикали. При этом она не может «перепрыгивать» через стоящие на ее пути фигуры.

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

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

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

Первая строка входного файла 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 массива, один на горизонталь, другой на вертикаль, но реализовать не смог. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
pav1uxa
1710 / 1550 / 599
Регистрация: 23.01.2014
Сообщений: 5,601
Завершенные тесты: 1
14.10.2015, 19:52     Задача "Ладья в Лабиринте" #2
ilyasoloma, Могу сказать что задача на теорию графов. Пока их не изучите - будет не очень просто ее решить
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
14.10.2015, 20:10     Задача "Ладья в Лабиринте" #3
pav1uxa, при чём тут теория графов? Ну то есть её тоже можно за уши притянуть сюда, но гораздо проще и удобнее не грузить себе мозг теорией, а реализовать какой-нибудь из изначально известных алгоритмов "поиска пути".
Поиск пути это ну настолько задроченная всеми задача, что реализовать её можно(и нужно), не задумываясь особо о графах как таковых.
Гуглим алгоритмы А-стар, волновой, Дейстры и.т.д. и радуемся.
https://www.google.com/search?q=А-стар
https://www.google.com/search?q=волновой+алгоритм
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
14.10.2015, 20:17     Задача "Ладья в Лабиринте" #4
Цитата Сообщение от ilyasoloma Посмотреть сообщение
. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
Задача на модификацию алгоритм Дейкстры поиска пути. Работает аналогично закраске с затравкой. Начинаете с текущего положения ладьи, запишите в него 0. запишите во все соседние клетки в которые возможен ход 1 и направление. В их соседей в которые ход возможен без изменения направления тоже 1 в остальные в которые возможен - 2, если там нет 1. и так дальше прибавляя 1 при изменении направления пока не дойдете до конечной точки. Число в конечной точке и будет количеством ходов.

Добавлено через 4 минуты
[/
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов?
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных.
Абсолютно естественно что теория графов тут вообще ни при делах .
pav1uxa
1710 / 1550 / 599
Регистрация: 23.01.2014
Сообщений: 5,601
Завершенные тесты: 1
14.10.2015, 20:57     Задача "Ладья в Лабиринте" #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов? Ну то есть её тоже можно за уши притянуть сюда, но гораздо проще и удобнее не грузить себе мозг теорией,
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Гуглим алгоритмы А-стар, волновой, Дейстры и.т.д. и радуемся.
Ну давайте погуглим:
Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе.
Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Как Вы думаете, человек, который даже не представляет что такое граф, ребро, вершина и так далее, легко разберется в этих алгоритмах? Это все равно что учиться читать не зная букв.
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
14.10.2015, 21:56     Задача "Ладья в Лабиринте" #6
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
при чём тут теория графов?
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
волновой, Дейстры
эти алгоритмы на графах используются
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
14.10.2015, 23:47     Задача "Ладья в Лабиринте" #7
Ой-ой, ну всё! заклевали...
Только вот одно слово вы пропускаете мимо глаз. Теория графов, теория! А алгоритмы поиска пути и тем более их реализация на С++ это уже практика.
И не надо смешивать. Следуя вашим советам, человек пойдёт читать толстый томик высшей математики и никогда к нам не вернётся.
А я ему сказал погуглить конкретные примеры алгоритмов, с названиями, программы для которых на С++ давно написаны.
И ему не следует заморачиваться даже о внутреннем устройстве этих программ, что уж тем более говорить о математических выкладках за ними?

Добавлено через 5 минут
Цитата Сообщение от pav1uxa Посмотреть сообщение
Как Вы думаете, человек, который даже не представляет что такое граф, ребро, вершина и так далее, легко разберется в этих алгоритмах?
легко
google+название алгоритма+copy+paste
а по вашим советам он заснёт на учебнике математики, перечитывая очередной раз определение 100500го термина
граф, ребро, вершина ....ориентированно связный полный двудольный k-хроматический гиперграф.
Очень нужный термин.
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
15.10.2015, 00:14     Задача "Ладья в Лабиринте" #8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Очень нужный термин.
Пока не осилит понятие древовидный граф алгоритм неосилит
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
легко google+название алгоритма+copy+paste
Легко превратится в быдлокодера. Если не въехал алгоритм Дейкстры и остальные на нем основанные тут в чистом виде не пойдут, их модифицировать надо.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а по вашим советам он заснёт на учебнике математики,
Программист - это в первую очередь математик. Знаешь сколько раза пытаясь заснуть на учебнике/cправочнике по математике просыпался лежа головой на клавиатуре?
ilyasoloma
0 / 0 / 0
Регистрация: 27.09.2015
Сообщений: 12
15.10.2015, 10:05  [ТС]     Задача "Ладья в Лабиринте" #9
Сегодня ещё раз вернулся к ней, решил, что рациональным решением будут ввод двумерного массива и обработка его волновым алгоритмом. Днях попытаюсь сделать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2015, 17:59     Задача "Ладья в Лабиринте"
Еще ссылки по теме:

Составить программу,которая выведет "Да","Нет","на границе" C++
Зачем перегружать операторы "++", "<<", ">>" и что они дают? C++
Поменять знак " $ " на " * " к первому вхождению символа " ? " C++

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

Или воспользуйтесь поиском по форуму:
Lensato
49 / 49 / 24
Регистрация: 07.10.2015
Сообщений: 170
11.11.2015, 17:59     Задача "Ладья в Лабиринте" #10
ilyasoloma, если вы решили эту задачу, то я бы хотел сравнить со своим решением.
Мой вариант (приложил) быстро решает таблицы до 400х400.
Там конечно небольшой бардак и плохая оптимизация, но мне интересна ваша идея.
Лучше сразу оптимизировать более качественный алгоритм.
Вложения
Тип файла: zip rook.zip (9.0 Кб, 5 просмотров)
Yandex
Объявления
11.11.2015, 17:59     Задача "Ладья в Лабиринте"
Ответ Создать тему
Опции темы

Текущее время: 18:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru