Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
116 / 115 / 64
Регистрация: 03.06.2013
Сообщений: 582

Кратчайший путь

16.09.2016, 20:25. Показов 1073. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем привет, есть лабиринт(массив 1- проход, 0 - стена)

Есть написанная не мной функция, которая ищет возможный путь, но она не находит кратчайший.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public void FindWave(int startX, int startY, int targetX, int targetY)
        {
            bool add = true;
            int[,] cMap = new int[Map.GetLength(0), Map.GetLength(1)];
            int x, y, step = 0;
            for (y = 0; y < Map.GetLength(0); y++)
                for (x = 0; x < Map.GetLength(1); x++)
                {
                    if (Map[y, x] == 0)
                        cMap[y, x] = -2;//индикатор стены
                    else
                        cMap[y, x] = -1;//индикатор еще не ступали сюда
                }
            cMap[targetX, targetY] = 0;//Начинаем с финиша
            while (add == true)
            {
                add = false;
                for (y = 0; y < Map.GetLength(1); y++)
                    for (x = 0; x < Map.GetLength(0); x++)
                    {
                        if (cMap[x, y] == step)
                        {
 
                            //Ставим значение шага+1 в соседние ячейки (если они проходимы)
                            if (y - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1)
                                cMap[x, y - 1] = step + 1;
                            if (x - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1)
                                cMap[x - 1, y] = step + 1;
 
                            if (y + 1 < Map.GetLength(1) && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1)
                                cMap[x, y + 1] = step + 1;
                            if (x + 1 < Map.GetLength(0) && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1)
                                cMap[x + 1, y] = step + 1;
                        }
                    }
                step++;
 
                add = true;
                if (cMap[startY, startX] == -1)//решение найдено
                    add = true;
                if (step > Map.GetLength(0) * Map.GetLength(1))//решение не найдено
                    add = false;
            }
}
Вот в конце концов, есть массив cMap, в котором есть "веса" пути, и надо как то от конца пройти в начало по кратчайшему.
Вопрос. Как пройти, не пойму.(
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.09.2016, 20:25
Ответы с готовыми решениями:

Найти кратчайший путь
Всем привет, кто может, помогите: Дан двумерный массив, нужно найти кратчайший путь от левого нижнего элемента до правого верхнего...

Кратчайший путь в матрице
Имеется двумерная матрица. Каждая ячейка имеет вес указанный в матрице, необходимо пройти наименьшее количество шагов имея сумму n. Начиная...

Программа определяющая кратчайший путь
Разработать программу определяющая кратчайший путь с#

3
9944 / 2945 / 496
Регистрация: 05.10.2013
Сообщений: 8,005
Записей в блоге: 241
18.09.2016, 13:40
А почему вы не хотите реализовать алгоритмы A star или волновой алгоритм? Или у вас по заданию нужно придумать уникальный собственный?
0
 Аватар для ata
269 / 253 / 186
Регистрация: 28.10.2015
Сообщений: 723
18.09.2016, 14:06
ИМХО, для учебного задания можно тупо реализовать поиск в ширину, тем более что и A*, и Lee - его вариации. Если топикстартеру все еще надо, могу написать такой алгоритм. Он жутко неэффективный, но зато простой для понимания.
0
116 / 115 / 64
Регистрация: 03.06.2013
Сообщений: 582
18.09.2016, 16:01  [ТС]
ata, 8Observer8, всем спасибо, всё дописал. Голова просто не варила вечером, а решение нужно было срочно..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.09.2016, 16:01
Помогаю со студенческими работами здесь

Кратчайший путь в графе: ошибка в программе
Подскажите, пожалуйста, что не так? Программная реализация алгоритма Форда-Беллмана, поиск кратчайшего пути в графе using System; ...

Определить кратчайший путь между вершинами
Для графа считанного из фала определить кратчайший путь между вершинами, заданными в режиме диалога. Изучить и использовать алгоритм...

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

Найти кратчайший путь в двухмерном массиве (FormAplication)
мне нужно найти кротчайший путь в двухмерном массиве,и надо написать эту программу при помощи FormAplication,как тут можно разделить окно...

Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде
У меня есть прога, которая находит кратчайший путь по алгоритму дейкстры, с графическим оформлением, нужна помощь с описанием работы данной...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Контроль уникальности заводского номера - вариант №2
Maks 24.03.2026
В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
Контроль уникальности заводского номера - вариант №1
Maks 23.03.2026
Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения
anaschu 22.03.2026
e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
Программный отбор элементов справочника по группе
Maks 22.03.2026
Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .
Как я обхитрил таблицу Word
Alexander-7 21.03.2026
Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru