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

Найти самый короткий путь от точки до точки в матрице - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Shagen
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 44
09.10.2012, 21:29     Найти самый короткий путь от точки до точки в матрице #1
Народ, помогите...
Такая задача, имеется массив символов(char arr[][]) в котором в рандомных местах установлены препятствия(к примеру символы '*') и имеем 2 точки, нужно найти самый короткий путь от 1й точки ко 2й, двигаться можно только по верикали или горизонтали(двигаться по диагонали нельзя).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2012, 21:29     Найти самый короткий путь от точки до точки в матрице
Посмотрите здесь:

C++ Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки.
C++ Наименьший путь от одной точки до другой
Как найти координаты точки на прямой удаленной от заданной точки на х C++
Задача (вывести длину кратчайшего пути от точки до точки.) C++
C++ не получается задачка (Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
actium
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 3
10.10.2012, 00:15     Найти самый короткий путь от точки до точки в матрице #2
используй очередь
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 00:26     Найти самый короткий путь от точки до точки в матрице #3
Вроде бы это динамическое программирование
вам для чего это надо - это задачка с какого-то сайта и есть ограничения по времени или это задачка из универа? если второе, то к какой теме это приурочено? случаем, не к рекурсии?
Shagen
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 44
10.10.2012, 10:15  [ТС]     Найти самый короткий путь от точки до точки в матрице #4
Второе, не важно к какой теме, с++ мы давно прошли(по крайней мере основы) задача заключается в следующем: создать класс с закрытым членом-динамическим 2хмерным массивом символов, конструктор имеет 2 аргумента(стороны массива), есть еще несколько открытых функций: показать массив, поставить на указанное место препятствие, назначить те самые 2 точки ну и найти самый короткий путь между ними, обходя, естественно, препятствия...Не важно что использовать перезагрузку функций, рекурсию, лямбда-выражения и т.д. мы давно прошли...Все сделал за 20 минут, но вот с алгоритмом поиска кратчайшего пути не могу справится вот уже 3 недели
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 11:08     Найти самый короткий путь от точки до точки в матрице #5
Я сам не большой знаток динам/программирования. На форуме есть ребята, которые в этом разбираются гораздо лучше. Если увидят вашу тему, то наверняка выдадут вам оптимальный алгоритм)
А я сам могу предложить самое простое решение (но и самое медленное) - рекурсия. Или разворачиваете свой массив как граф и ищите кратчайший путь уже в графе.
Shagen
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 44
10.10.2012, 11:48  [ТС]     Найти самый короткий путь от точки до точки в матрице #6
Совет про граф слышу не в первый раз, но я с графами раньше никогда не работал, что же касается рекурсии, то я пробывал, но всегда нахожу какой-то косяк в алгоритме, пробывал даже вычислить все возможные пути и выбрать самый короткий из них, тоже ничего путного не вышло
actium
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 3
10.10.2012, 12:23     Найти самый короткий путь от точки до точки в матрице #7
я же писал это примитивная очередь. (Поищи на википедии есть, и ещё...)

добавил 1 точку в очередь она нашла вторую. Теперь коротко расскажу как: В общем добавил первую точку. В каком то массиве записал это. Увеличил счётчик начала(на вики как start описана) А потом пока start!=finish берёшь ту предыдущую точку и пытаешься идти в 4 стороны, куда пройти можно добавяешь в массив. И так дальше пока не найдёшь вторую точку. Кароче по-гугли код там предельно понятно.

что касается динамики... она тут подольше будет. Я б писал такую. Та точка в которой мы стоим взял бы за 1 шаг, на следующем проходе по массиву если в соседней точке 1 и в данную точку можно пройти то в данной клетке массива 2, и т.д. В итоге в конце в конечной точке будет тоже число за которое ты дошёл до этой точки. Но динамика гораздо медленнее тут... Это типичная задача на ОЧЕРЕДЬ!
Кот Ангенс
 Аватар для Кот Ангенс
317 / 267 / 37
Регистрация: 24.05.2012
Сообщений: 629
10.10.2012, 13:42     Найти самый короткий путь от точки до точки в матрице #8
Реализовал алгоритм Дейкстры.
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
#include <cstdlib>
#include <vector>
 
typedef unsigned /*short*/ dist_t;
typedef unsigned short fsize_t;
 
struct Field {
    dist_t dist;
    bool pathable;
 
    Field() {
        dist = dist_t(-1);//Максимальное значение
        pathable = true;
    }
};
 
class Graph {
    Field* f;
    fsize_t w, h;
 
protected:
    Field& F(fsize_t x, fsize_t y) {
        return f[x + y * w];
    }
 
    void SetDist(fsize_t x, fsize_t y, dist_t d) {
        if (d < F(x, y).dist) {
            F(x, y).dist = d;
            if (x && F(x - 1, y).pathable)
                SetDist(x - 1, y, d + 1);
            if (x < w - 1 && F(x + 1, y).pathable)
                SetDist(x + 1, y, d + 1);
            if (y && F(x, y - 1).pathable)
                SetDist(x, y - 1, d + 1);
            if (y < h - 1 && F(x, y + 1).pathable)
                SetDist(x, y + 1, d + 1);
        }
    }
 
public:
    Graph() {
        f = NULL;
        w = h = 0;
    }
 
    Graph(fsize_t width, fsize_t height) {
        f = new Field[width * height];
        w = width;
        h = height;
    }
 
    ~Graph() { delete[ ] f; }
 
    void Resize(fsize_t width, fsize_t height) {
        delete[ ] f;
        f = new Field[width * height];
        w = width;
        h = height;
    }
 
    void SetPathable(fsize_t x, fsize_t y, bool state) {
        F(x, y).pathable = state;
    }
 
    /*
        0 - вверх
        1 - влево
        2 - вправо
        3 - вниз
    */
 
    std::vector<char> Find(fsize_t x0, fsize_t y0, fsize_t x1, fsize_t y1) {
        SetDist(x0, y0, 0);
        dist_t i = F(x1, y1).dist;
        std::vector<char> v(i);
        //Идем в обратном направлении, от конца к началу
        while (i--)
            if (y1 && F(x1, y1 - 1).dist < F(x1, y1).dist) {
                y1--;
                v[i] = 3;
            } else if (x1 && F(x1 - 1, y1).dist < F(x1, y1).dist) {
                x1--;
                v[i] = 2;
            } else if (x1 < w - 1 && F(x1 + 1, y1).dist < F(x1, y1).dist) {
                x1++;
                v[i] = 1;
            } else {
                y1++;
                v[i] = 0;
            }
        return v;
    }
};
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
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
void PrintPath(char d) {
    switch (d) {
        case 0: cout << "up\n"; break;
        case 1: cout << "left\n"; break;
        case 2: cout << "right\n"; break;
        default: cout << "down\n";
    }
}
 
int main() {
    /*
          0 1 2
        0 @ # $
        1 . # .
        2 . . .
    */
    Graph g(3, 3);
    g.SetPathable(1, 0, false);
    g.SetPathable(1, 1, false);
    vector<char> v = g.Find(0, 0, 2, 0);
    for_each(v.begin(), v.end(), PrintPath);
    cout << endl;
    /*
          0 1 2 3
        0 $ # . .
        1 . . # .
        2 # . . .
        3 . # . #
        4 @ . . .
    */
    g.Resize(4, 5);
    g.SetPathable(1, 0, false);
    g.SetPathable(2, 1, false);
    g.SetPathable(0, 2, false);
    g.SetPathable(1, 3, false);
    g.SetPathable(3, 3, false);
    v = g.Find(0, 4, 0, 0);
    for_each(v.begin(), v.end(), PrintPath);
    cin.get();
}
Миниатюры
Найти самый короткий путь от точки до точки в матрице  
Кот Ангенс
 Аватар для Кот Ангенс
317 / 267 / 37
Регистрация: 24.05.2012
Сообщений: 629
10.10.2012, 14:01     Найти самый короткий путь от точки до точки в матрице #9
Кстати, можно заменить хвостовую рекурсию циклом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SetDist(fsize_t x, fsize_t y, dist_t d) {
    while (d < F(x, y).dist) {
        F(x, y).dist = d;
        if (x && F(x - 1, y).pathable)
            SetDist(x - 1, y, d + 1);
        if (x < w - 1 && F(x + 1, y).pathable)
            SetDist(x + 1, y, d + 1);
        if (y && F(x, y - 1).pathable)
            SetDist(x, y - 1, d + 1);
        if (!(y < h - 1 && F(x, y + 1).pathable))
            return;
        y++;
        d++;
    }
}
Shagen
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 44
10.10.2012, 15:11  [ТС]     Найти самый короткий путь от точки до точки в матрице #10
Кот Ангенс, спасибо большое, осталось все это понять и переварить
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.10.2012, 16:30     Найти самый короткий путь от точки до точки в матрице #11
Цитата Сообщение от actium Посмотреть сообщение
Это типичная задача на ОЧЕРЕДЬ!
абсолютно верно.
Shagen
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 44
10.10.2012, 19:22  [ТС]     Найти самый короткий путь от точки до точки в матрице #12
Про очереди почитал на вики, обьяснения довольно туманны, а примеров реализации алгоритма на каком-нибудь языке программирования вообще нет, вариант с графами хотя бы понятен
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2012, 22:43     Найти самый короткий путь от точки до точки в матрице
Еще ссылки по теме:

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников C++
Найти минимальное расстояние от точки до точки C++
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки C++

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

Или воспользуйтесь поиском по форуму:
actium
0 / 0 / 0
Регистрация: 08.10.2012
Сообщений: 3
10.10.2012, 22:43     Найти самый короткий путь от точки до точки в матрице #13
эм.... могу на Pascal дать! На С++ переделать просто. Ну в принципе на вот, если разберёшься норм, нет то потом на с++ переписать могу... хотя блин ладно щас напишу:
блин долго напишу вот так псевдокодом почти...

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
#include <stdio.h>
 
char a[10][10];
const maxQ=100;
int q1,q2,qx[maxQ],qy[maxQ],qz[maxQ],ans=-1,x1,y1,x2,y2;
 
int add(int y, int x, int z){   // y,x - координаты рассматриваемой точки, z - шаг на котором до неё дошли.
    if (a[y,x]!="*") return 0;  // если по клетке пойти нельзя (преграда) выход из процедуры
    a[y][x]='#';     // мусорим клетку чтоб не пойти второй раз
    qx[q1]=x;
    qy[q1]=y;        // запоминаем клетку и с какого раза пришли
    qz[q1]=z;
    if (q1>maxQ) q1=0;     // опять же зацикливание... внизу писал
    if( (y==y2)&(x==x2)){  // проверка если вдруг это клетка куда надо прийти то запоминаем на каком щаге и выходим.
        q1=q2+1;
        ans=z;
    }
    return 1;
}
 
void main(){
//ну тут чтение размера массива, массив, стартовую точку (y1,x1) и конечную (y2,x2)
    q1=0; q2=0;
    add(y1,x1,0);   
    while (q1!=q2){  //пока начало очереди не дошло до конца
        x=qx[q2];
        y=qx[q2];            // присваиваем точку из очереди
        z=qz[q2];
        add(y-1,x,z+1);     // попытка пойти во все 4 направления вверх, вниз, влево, вправо
        add(y+1,x,z+1);
        add(y,x-1,z+1);
        add(y,x+1,z+1);
        q2++;           // отодвигаем конец
        if (q2>maxQ) q2=0;   // зацикливание очереди, в принципе если не разбираешься можно опустить.
    }
    printf("%d",ans);
}
P.S: по "*" можно ходить по "#" нельзя!
Yandex
Объявления
10.10.2012, 22:43     Найти самый короткий путь от точки до точки в матрице
Ответ Создать тему
Опции темы

Текущее время: 14:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru