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

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

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

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

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

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

Добавлено через 19 минут
и в идеале, что бы он работал с вектором строк
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2012, 19:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск пути (C++):

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

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

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

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

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

Поиск пути в лабиринте - 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...

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

Добавлено через 17 секунд
Можно его увидеть?
0
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
+ - стена
@ - кажется вход
$ - кажется выход
если не так, то наоборот
1
17.07.2012, 00:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2012, 00:06
Привет! Вот еще темы с ответами:

Поиск пути на поле из шестиугольников - C++
Всем привет)) Нужна ваша помощь. В одной веб-игре нужно написать бота, игра в жанре ммо рпг (пошаговая). Я столкнулся с проблемой...

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

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

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


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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