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

Поиск кратчайшего пути на клетчатом поле. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Файлы , массивы и структура http://www.cyberforum.ru/cpp-beginners/thread259328.html
То что нужно сделать : Разработать программу на С, позволяющую: 1. Добавлять данные структуры с указанными полями в файл 2. Просматривать структуры из файла 3. Выполнять дополнительную операцию...
C++ C++ Ошибка сегментирования Вот листинг файла: #include <fstream> #include <iostream> #include <vector> using namespace std; int main() { char theFile, theChar; http://www.cyberforum.ru/cpp-beginners/thread259314.html
C++ Проверка строчьки на наличие букв
Как проверить введенную строку на наличие букв\знаков? Помогите пожалуйста...
C++ Вычислить значение выражения
Вобщем задание таково - нужно решить пример тремя циклами в одной программе.(do - while , while (с выводом библиотек c++), for) пример такой: y=441*cos(x)+ П(от i=2 до N) (4.1*cos(x) + i^(1/3)) ...
C++ Дешифратор по имеющемуся словарю http://www.cyberforum.ru/cpp-beginners/thread259300.html
Дешифратор почему-то не работает.. на входе подается зашифрованный текст, имея "эталоны" словоформ нужно расшифровать этот текст. Ко всем символам зашифрованного текста прибавляются ключи от 1до 255...
C++ вроде все просто #include "stdafx.h" #include <iostream> #include <ctime> using namespace std; int main() { int mas, a; srand (time(NULL)); for(int i = 0; i < 10; i++) подробнее

Показать сообщение отдельно
nixe

Поиск кратчайшего пути на клетчатом поле. - C++

17.03.2011, 21:10. Просмотров 2295. Ответов 1
Метки (Все метки)

Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти кратчайший путь из начальной клетки в конечную.

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

Имеющиеся на данный момент идеи:
  • поле имплементовать двухразмерным массивом, где клетки, куда можно наступать будут 0, клетки куда нельзя (камни, лес, что угодно, если предполагать, что у нас какая-нибудь карта ^^) - 1. Или наоборот, не принципиально пока.
  • каждую клетку воспринять как вершину графа. Таким образом, вершины, находящиеся в клетках, куда нельзя наступать, будут оторваны от графа, а вершины, соответствующие "обычным" клеткам, будут соответственно иметь от 1 до 4 граней.
  • таким образом, вся задача конвертируется на задачу поиска кратчайшего пути в графе => да поможет мне Дийкстра.

Что смущает в собственой идее - с ростом размера поля размер матрицы, описывающей граф, будет расти до неописуемых размеров, ибо уже для поля 8х8 (64 вершины), надо массив 64х64 для описания графа. Я первокурсник, опыта с графами, кроме теоретического, - нет, поэтому такие цифры кажутся неоправданно большими.

Критикуйте, стебите, буду только рада. Ещё раз, пожалуйста, прошу, подсказывайте аккуратно! Выводы хочу сделать сама!
И заранее спасибо, тем, кто-таки возьмётся.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru