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

Поиск кратчайшего пути на клетчатом поле. - 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)) #include<stdio.h> #include<math.h> #include<iostream.h> #include<iomanip.h> using namespace std; int main() {
C++ Дешифратор по имеющемуся словарю http://www.cyberforum.ru/cpp-beginners/thread259300.html
Дешифратор почему-то не работает.. на входе подается зашифрованный текст, имея "эталоны" словоформ нужно расшифровать этот текст. Ко всем символам зашифрованного текста прибавляются ключи от 1до 255 и потом получившееся при сложении с ключом сравнивается с элементами в словаре.. #include <iostream> #include <list> #include <vector> #include <fstream> #include <Cstring> #include <cctype>...
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
Сообщений: n/a
17.03.2011, 21:10     Поиск кратчайшего пути на клетчатом поле.
Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти кратчайший путь из начальной клетки в конечную.

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

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

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

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