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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сформировать одномерный массив на основе двух других массивов http://www.cyberforum.ru/cpp-beginners/thread667481.html
Даны два массива: А, состоящий из N элементов и В, состоящий из N элементов. Сформировать массив C по следующему правилу Результат распечатать в виде: Число элементов: Исходный массив А: Исходный массив В: Новый массив С:
C++ COORD position = {0,0}; - как это работает? Здравствуйте. Разбираю код двух программ: "Сапер" и "Змейка" и в каждой из них есть, вроде бы, функция COORD. То, что COORD position = {0,0}; отвечает за местоположение некоторой точки с координатами (x,y) - это понятно, но как оно работает? http://www.cyberforum.ru/cpp-beginners/thread667479.html
C++ fstream
Всем доброго дня! Как с помощью библиотеки fstream вывести содержимое файла на экран??
C++ Перевод программы с Pascal на С++
1. procedure TForm1.Button1Click(Sender: TObject); var i,k,n:integer; x,y,S:array of real; D:real; begin n:=StrToInt(edit1.Text); D:=StrToInt(edit2.Text); i:=0; for K:=1 to n do
C++ Обработка массива http://www.cyberforum.ru/cpp-beginners/thread667464.html
Помогите напи сать программу по заданному исходнику под Visual C++ Задание: Заданы два массива X=(x1,x2,...,xn) и Y = (y1,y2,...,ym), в состав которых входят натуральные числа, причем в каждом из этих массивов нет повторяющихся элементов. Сформировать массив Z, включив в него все элементы, которые одновременно содержатся в массиве X и массиве Y. Подсчитать количество неповторяющихся...
C++ Программа для операций с комплексными числами На базе приведенного ниже класса и примера его использования надо реализовать программу работы с комплексными числами, что бы выполнялись следующие требования: 1. Программа должна позволять выполнять следующие основные операции на комплексными числами: + - * / ++(унарный плюс) --(унарный минус) 2. Программа должна позволять выполнять приведенные выше операции как над парой комплексных чисел,... подробнее

Показать сообщение отдельно
Кот Ангенс
317 / 267 / 38
Регистрация: 24.05.2012
Сообщений: 629
10.10.2012, 13:42     Найти самый короткий путь от точки до точки в матрице
Реализовал алгоритм Дейкстры.
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();
}
Миниатюры
Найти самый короткий путь от точки до точки в матрице  
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru