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

Не работает рекурсивная функция - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ C++ to C converter (OOP C) http://www.cyberforum.ru/cpp/thread1846824.html
Всем привет! Не встречал ли кто подобного конвертера, который может код на языке высокого уровня конвертировать в Си-шный код (плохочитаемый, для выкладки в качестве опенсорца для любопытных и для...
C++ H323Plus + PTLib: PDU Read Error: Timed Out на приемном канале Здравствуйте товарищи, помогите кто чем может разобраться с ошибкой. Анамнез: Есть самописная софтина которая должна осуществлять телефонную связь с удаленным терминалом по протоколу H.323. При... http://www.cyberforum.ru/cpp/thread1845334.html
Структура с не известными переменными C++
Добрый вечер. Допустим есть структура (не моя) с некоторыми переменными. Можно ли сделать свою структуру, но, при этом заранее указать переменным этой структуры нужное смещение? Пример: ...
C++ Стандарт C++ вышел на русском
Небезызвестный Евгений Зуев выполнил таки свое обещание и перевел Стандарт. Книжка доступна только (настолько мне известно) здесь. Цена кусается, мнения у всех по этому вопросу разные. Смотрите...
C++ Как разреженную матрицу перевести в формат CRS? http://www.cyberforum.ru/cpp/thread1843709.html
Привет кодеры! Моя задача заключается в том чтобы перемножить две разреженные матрицы. Но для того чтобы это сделать нужно эти матрицы привести к виду CRS. Я весь день а то и два не могу понять как...
C++ Как пишут программы благодаря которым можно управлять объектами? Как пишут программы при помощи которых можно управлять предметами у себя дома? Например, когда кто-то откроет холодильник, придет сообщение на смартфон или компьютер о том то что холодильник был... подробнее

Показать сообщение отдельно
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 169
10.11.2016, 17:14
Алгоритм Дейкстры. У вас каждая вершина графа связана с 4 соседними или меньше, если есть препятствия. И цена шага везде 1.

Добавлено через 26 минут
Единственно можно немного упростить, можно убрать проверку на сумму длин, потому что он равен шагу алгоритма (из-за того, что все ребра 1), а каждый посещенный узел отмечается флагом out уже на следующем шаге. Алгоритм завершает работу когда не остаётся узлов помеченных как visited и при этом не помеченных как out (иначе говоря цикл идет по узлам visited, но только по тем которые не получили флаг out в самом начале все флаги сброшены и только у стартовой точки visited). Могут остаться узлы не помеченные как visited, если препятствия их окружили, для того, чтобы отличать их от стартовой точки, стоит назначить параметру длина пути некоторое начальное значение -1 например, а стартовая точка 0 будет.

Добавлено через 4 минуты
вместо флага visited можно сравнивать значение поля с шагом цикла, а out тогда значение меньше этого шага. (упрощение которое следует опять из-за того, что все ребра 1)

Добавлено через 5 минут
Для того чтобы не бегать по всему массиву и сравнивать его с номером шага алгоритма, можно номера ячеек которые получили свой параметр длины пути в другой массив складывать. (это уже оптимизации)
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru