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

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

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

Поиск пути - C++

16.07.2012, 19:10. Просмотров 839. Ответов 6
Метки нет (Все метки)

есть таблица в которой некоторые клетки заняты и некоторые свободны.
нужен алгоритм нахождения пути из точку а(х1,у1) в точку б(х2,у2).
Двигаться можно только в четыре направления "вверх", "вниз", "влево", "вправо".

Добавлено через 19 минут
и в идеале, что бы он работал с вектором строк
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2012, 19:10     Поиск пути
Посмотрите здесь:

Поиск пути - C++
Здравствуйте, посмотрите пожалуйста код и прокомментируйте на сколько рационально я использую память и вычислительную мощность?:-#include...

Поиск пути - C++
Дан лабиринт из n комнат и матрица, в которой содержится информация о наличии прохода между любыми двумя комнатами, независимо от их...

Поиск пути - C++
Люди добрые,помогите пожалуста с задачкой: Дан двумерный массив А состоящий из нулей и единиц, с клавиатуры вводятся координаты двух...

Поиск пути в лабиринте - C++
Доброго времени суток! есть задача пройти лабиринт {1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1...

поиск длины пути - C++
Всем доброго утра Ребята подскажите пожалуйста алгоритм дана матрица расстояний n*n, в ячейках расположены расстояний между i и j...

Поиск пути в лабиринте - C++
Есть двухмерный массив : 1 - препятствие, 0 - проход. Нужно найти кратчайший путь от одной точки до другой. У меня есть волновой...

Длина пути (поиск в ширину) - C++
В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Гарантируется, что путь существует. Входные...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.07.2012, 20:25     Поиск пути #2
Обычный bfs(поиск в ширину, волновой алгоритм).
Barterio
0 / 0 / 0
Регистрация: 14.07.2012
Сообщений: 14
16.07.2012, 20:44  [ТС]     Поиск пути #3
а есть реализация(код)?
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.07.2012, 20:47     Поиск пути #4
А что должна вывести программа?
Длину кратчайшего пути или сам кратчайший путь?
Если второе, то в каком виде?
Sanek911
4 / 4 / 0
Регистрация: 04.12.2009
Сообщений: 42
16.07.2012, 23:32     Поиск пути #5
Цитата Сообщение от Barterio Посмотреть сообщение
а есть реализация(код)?
имеется
Barterio
0 / 0 / 0
Регистрация: 14.07.2012
Сообщений: 14
16.07.2012, 23:40  [ТС]     Поиск пути #6
должна вывести кратчайший путь в виде букв(вверх, вниз, влево, вправо)

Добавлено через 17 секунд
Можно его увидеть?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2012, 00:06     Поиск пути
Еще ссылки по теме:

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

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

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

Поиск оптимального пути в трехмерной карте - C++
Доброго времени суток. Не получается решить задачу: Существует 3-х мерная карта ячеек произвольной известной заранее размерности,...

Волновой алгоритм - поиск минимального пути - C++
Доброго времени суток всем. Не могу въехать в алгоритм волновой для поиска минимального пути. Видел кучу примеров с готовым кодом, читал,...


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

Или воспользуйтесь поиском по форуму:
Sanek911
4 / 4 / 0
Регистрация: 04.12.2009
Сообщений: 42
17.07.2012, 00:06     Поиск пути #7
тебе повезло студент

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
 
typedef std::vector<std::pair<char, std::pair<int, std::pair<int, int> > > > VectorOfPairs;
 
static const int mx = 9, my = 9;
static const int N = 8, M = 11;
static bool findWay = false;
 
struct MyClass{
    char _symbol;
    int _value_of_wave;
    int _parent_x;
    int _parent_y;
 
    MyClass(char symbol = ' ', int value_of_wave = 0, int parent_x = 0, int parent_y = 0) 
        : _symbol(symbol), _value_of_wave(value_of_wave), _parent_x(parent_x), _parent_y(parent_y)
    {}
};
 
void DoWater(std::vector<VectorOfPairs>& matr, int y, int x, int& cnt){
    int empty = 0;
    //верхняя клетка
    if ((y - 1) > -1) 
        //проверка клетки на наличие конца
        if (matr[y - 1][x].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y - 1][x].second.second.first = y;
            matr[y - 1][x].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y - 1][x].second.first == empty){
                matr[y - 1][x].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y - 1][x].second.second.first = y;
                matr[y - 1][x].second.second.second = x;
            }
    //правая клетка
    if ((x + 1) < ::M)
        //проверка клетки на наличие конца
        if (matr[y][x + 1].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y][x + 1].second.second.first = y;
            matr[y][x + 1].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y][x + 1].second.first == empty){
                matr[y][x + 1].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y][x + 1].second.second.first = y;
                matr[y][x + 1].second.second.second = x;
            }
    //нижняя клетка
    if ((y + 1) < ::N)
        //проверка клетки на наличие конца
        if (matr[y + 1][x].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y + 1][x].second.second.first = y;
            matr[y + 1][x].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y + 1][x].second.first == empty){
                matr[y + 1][x].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y + 1][x].second.second.first = y;
                matr[y + 1][x].second.second.second = x;
              }
    //левая клетка
    if ((x - 1) > -1)
        //проверка клетки на наличие конца
        if (matr[y][x - 1].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y][x - 1].second.second.first = y;
            matr[y][x - 1].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y][x - 1].second.first == empty){
                matr[y][x - 1].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y][x - 1].second.second.first = y;
                matr[y][x - 1].second.second.second = x;
              }
}
 
void main()
{
    int begin_i = 0, begin_j = 0, //координаты входа
        end_i = 0, end_j = 0, //координыта выхода
        count = 1;
    bool noDoWater = false; //досрочное окончание поиска конца, если не было волны
    std::vector<VectorOfPairs> arr(N, VectorOfPairs(M));
 
    std::ifstream infile("C:\Labirint.txt");
//считывание лабиринта в массив
    if(!infile){
        std::cout << "Error";
        exit(1);
    }
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < M; ++j){
            infile.get(arr[i][j].first);
            if (arr[i][j].first == '@'){
                begin_i = i;
                begin_j = j;
                arr[i][j].second.first = 1;
                //запоминание начала координат старта
                arr[i][j].second.second.first = i;
                arr[i][j].second.second.second = j;
            }
            if (arr[i][j].first == '$'){
                end_i = i;
                end_j = j;
                arr[i][j].second.first = -1;
            }
            if (arr[i][j].first == '+'){
                arr[i][j].second.first = -2;
            }
        }
    }
 
//поиск пути
 
    int cnt = 1, //счетчик номера волны
        size_y = 0, size_x = 0, //размеры поля в кт. ищем нужный номер волны
        move_y = begin_i, move_x = begin_j, //начальные координаты квадрата в кт. производим поиск волны
        empty = 0; //условное обозначение пустой клетки
    do{
        noDoWater = true;
        //просмотр определенного участка поля и заполнение новых клеток водой
        for (int i = move_y; i <= (move_y + size_y); ++i)
            for (int j = move_x; j <= (move_x + size_x); ++j){
                if (arr[i][j].second.first == cnt){
                    DoWater(arr, i, j, cnt);
                    noDoWater = false;
                }
            }
        //изменение поля в кт. произойдет заполнение новых клеток водой
        //изменения начальных координат участка поля в кт. будет происходить поиск последней волны
        if (move_y > 0)
            --move_y;
        if (move_x > 0)
            --move_x;
        //изменение размеров поля
        if((move_y + size_y + 2) <= (N - 1))
            size_y += 2;
        if((move_x + size_x + 2) <= (M - 1))
            size_x += 2;
        ++cnt;
    }while((!noDoWater) && (!::findWay));
//вывод результата
    if(noDoWater)
        std::cout << "No way found" <<std::endl;
    else{
        int prev_y = 0, temp_y = end_i, prev_x = 0, temp_x = end_j;
        do{
            prev_y = temp_y;
            prev_x = temp_x;
            std::cout << prev_y << ' ' << prev_x << std::endl;
            if ((arr[prev_y][prev_x].first != '@') && (arr[prev_y][prev_x].first != '$'))
                arr[prev_y][prev_x].first = '*';
            temp_y = arr[prev_y][prev_x].second.second.first;
            temp_x = arr[prev_y][prev_x].second.second.second;
        }while((prev_y != begin_i) || (prev_x != begin_j));
    }
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            std::cout << arr[i][j].first;
 
    std::cout << std::endl;
}
свою благодарность можешь проявить
R336251197565 тут или
U302965972502 тут

забыл добавить: файл храни на C:\Labirint.txt
+ - стена
@ - кажется вход
$ - кажется выход
если не так, то наоборот
Yandex
Объявления
17.07.2012, 00:06     Поиск пути
Ответ Создать тему
Опции темы

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