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

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

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

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

14.10.2015, 10:52. Просмотров 713. Ответов 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 массива, один на горизонталь, другой на вертикаль, но реализовать не смог. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2015, 10:52     Задача "Ладья в Лабиринте"
Посмотрите здесь:

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

Задача "Кто старше?" (подскажите где ошибка в коде) - C++
Здравствуйте!подскажите где может быть ошибка, на сайте показывает частичное решение, Условие: Программа принимает три числа: возраст...

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...

Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" - C++
Здравствуйте! Не могу решить задачу из книги. Задача Введите целые данные, содержащие только нули и единицы (т.е. «двоичные»...

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером - C++
Гигабашня — самое высокое и глубокое здание в Киберленде. В ней 17 777 777 777 этажей, пронумерованных от  - 8 888 888 888 до...

Вычислить значение суммы. Задача с использованием "длинной арифметики". - C++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...

Структуры... Задача: "База сотрудников небольшой фирмы" - C++
По каждому сотруднику вводится следующая информация: • Фамилия, имя, отчество; • год и дата рождения; • пол; • стаж работы по...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
pav1uxa
1787 / 1627 / 621
Регистрация: 23.01.2014
Сообщений: 5,885
Завершенные тесты: 1
14.10.2015, 19:52     Задача "Ладья в Лабиринте" #2
ilyasoloma, Могу сказать что задача на теорию графов. Пока их не изучите - будет не очень просто ее решить
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
14.10.2015, 20:10     Задача "Ладья в Лабиринте" #3
pav1uxa, при чём тут теория графов? Ну то есть её тоже можно за уши притянуть сюда, но гораздо проще и удобнее не грузить себе мозг теорией, а реализовать какой-нибудь из изначально известных алгоритмов "поиска пути".
Поиск пути это ну настолько задроченная всеми задача, что реализовать её можно(и нужно), не задумываясь особо о графах как таковых.
Гуглим алгоритмы А-стар, волновой, Дейстры и.т.д. и радуемся.
https://www.google.com/search?q=А-стар
https://www.google.com/search?q=волновой+алгоритм
Fulcrum_013
661 / 729 / 72
Регистрация: 14.12.2014
Сообщений: 5,698
Завершенные тесты: 3
14.10.2015, 20:17     Задача "Ладья в Лабиринте" #4
Цитата Сообщение от ilyasoloma Посмотреть сообщение
. Пробовал вводить массив на всё количество знаков, а потом пропускать через условные операторы, но работает только в частных случаях.
Задача на модификацию алгоритм Дейкстры поиска пути. Работает аналогично закраске с затравкой. Начинаете с текущего положения ладьи, запишите в него 0. запишите во все соседние клетки в которые возможен ход 1 и направление. В их соседей в которые ход возможен без изменения направления тоже 1 в остальные в которые возможен - 2, если там нет 1. и так дальше прибавляя 1 при изменении направления пока не дойдете до конечной точки. Число в конечной точке и будет количеством ходов.

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

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

Задача "Гонки по улицам" (обход ориентированного графа) - C++
Здравствуйте,помогите с задачей,если можно с комметарием,чтобы разобраться.Спасибо На рисунке ниже изображен пример плана улиц для гонки....

Задача из книги "Програмирование - принципы и практика использования C++" - C++
Кто читал ету книгу, помогите разобратся с задачей с 12 главы. Никак не могу скомпилировать простую программу. Вот ее код: #include...

Задача "Максимальный подпалиндром" не могу поймать ошибку. - C++
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется...

Задача "Движение по клеткам таблицы" (Динамическое программирование) - C++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...

Создать класс Account. Задача из книги Дейтелов "Как програмировать на С++" - C++
Начал изучение С++, прочитал главу "Введение в классы и объекты" в книге Дейтелов "Как програмировать на С++", ничего не поняв прочитал её...


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

Или воспользуйтесь поиском по форуму:
_sitizen_
0 / 0 / 0
Регистрация: 27.04.2014
Сообщений: 4
25.12.2016, 23:19     Задача "Ладья в Лабиринте" #11
В данном случае оптимальным будем волновой метод поиска кратчайшего пути с распространением действия волны не только к соседним (от очередной ячейки элементам), а к краю свободной области.

PS посмотрите здесь: Ладья в лабиринте есть решение
всем кто будет кидать в меня камни: достали уже быдлокодеры, которые лишь указывают, куда нужно идти и что учить, хотя иногда, даже изучив теорию графов, иногда на мелочах тормозишь и не можешь сразу придумать решение, а ведь все что нужно - указать способ...
Yandex
Объявления
25.12.2016, 23:19     Задача "Ладья в Лабиринте"
Ответ Создать тему
Опции темы

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