0 / 0 / 0
Регистрация: 26.06.2017
Сообщений: 3
1

Лабиринт. Объяснить код

26.06.2017, 16:49. Показов 650. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет. Нашел на просторах вашего форума такой вот код:
Проверил, все работает. Может кто объяснить, как эта программа устроена, мне не совсем понятны структуры, функции и прочее. Заранее благодарен
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
#include "stdafx.h"
#include <stack>
#include <iostream>
#include <string>
#include <algorithm>
#include <locale>
 
const int OPEN_VAL = 0;
const int CLOSE_VAL = 1;
const int START_VAL = -1;
 
struct T_cell
{
    int i_;
    int j_;
    T_cell(int i, int j) : i_(i), j_(j)
    {}
 
    bool operator==(const T_cell& c)
    {
        return i_ == c.i_ && j_ == c.j_;
    }
 
    bool operator!=(T_cell c)
    {
        return !(*this == c);
    }
};
 
struct T_path_node
{
    T_cell  prev_cell_;
    T_cell  cur_cell_;
 
    T_path_node
        (
        T_cell  prev_cell,
        T_cell  cur_cell
        ) : prev_cell_(prev_cell), cur_cell_(cur_cell)
    {}
};
 
std::ostream& operator<<(std::ostream& os, const T_cell&  cell)
{
    os << "(" << cell.i_ << ", " << cell.j_ << ")";
    return os;
}
 
 
typedef std::stack<T_path_node>  T_path_stack;
 
bool fill_stack(T_path_stack&  path_stack)
{
    const int m = 9;
    const int n = 9;
    int labirint[][n] = { { 1, 1, 1, 1, 1, 0, 1, 1, 1 },
    { 1, 0, 0, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 1, 0, 0, 0, 0, 1 },
    { 1, 1, 0, 0, 0, 1, 1, 1, 1 },
    { 1, 1, 1, 1, -1, 1, 1, 1, 1 } };
 
    //Для каждого значения в клетке от START_VAL и меньше заполняем соседние клетки
    //со значением OPEN_VAL значением на единицу меньше, чем в текущей клетке.
    //Процесс заканчивается, когда мы заполняем клетку, стоящую с краю, либо, если 
    //при очередном проходе мы не заполнили ни одной клетки.    
    for (int cur_cell_val = START_VAL;; --cur_cell_val)
    {
        //У каждой клетки со значением cur_cell_val заполняем все соседние клетки
        //со значением OPEN_VAL значением cur_cell_val - 1.        
        int  start_stack_size = path_stack.size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (labirint[i][j] == cur_cell_val)
                {
                    //Обходим соседние клетки.
                    for (int  i_sosed = std::max(i - 1, 0);
                        i_sosed <= std::min(i + 1, m - 1); ++i_sosed)
                    {
                        for (int  j_sosed = std::max(j - 1, 0);
                            j_sosed <= std::min(j + 1, n - 1); ++j_sosed)
                        {
                            //Если столбцы или строки совпадают и клетка свободна, то:
                            if ((i_sosed == i || j_sosed == j)
                                && labirint[i_sosed][j_sosed] == OPEN_VAL)
                            {
                                labirint[i_sosed][j_sosed] = cur_cell_val - 1;
                                path_stack
                                    .push(
                                    T_path_node(
                                    T_cell(i, j),
                                    T_cell(i_sosed, j_sosed)
                                    )
                                    );
 
                                //Если клетка крайняя, то:
                                if (i_sosed == 0 || i_sosed == m - 1
                                    || j_sosed == 0 || j_sosed == n - 1)
                                {
                                    return true;
                                }//if(i_for_fill == 0 || i_for_fill == m - 1
                            }//if((i_sosed == i || j_sosed == j)
                        }//for(int  j_sosed = std::max(0, j - 1);                   
                    }//for(int  i_sosed = std::max(0, i - 1);
                }//if(labirint[i][j] == cur_cell_val)
            }//for(int j = 0; j < n; ++j)        
        }//for(int i = 0; i < m; ++i)        
        if (path_stack.size() == start_stack_size) return false;
    }//for(int cur_cell_val = START_VAL; ; --cur_cell_val)
}
 
void print_path(T_path_stack  path_stack)
{
    std::cout << "Маршрут в лабиринте от выхода до стартовой клетки:" << std::endl;
    for (;;)
    {
        T_cell  prev_cell = path_stack.top().prev_cell_;
        std::cout << path_stack.top().cur_cell_ << std::endl;
        if (path_stack.size() == 1)
        {
            std::cout << path_stack.top().prev_cell_ << std::endl;
            return;
        }
        while (path_stack.top().cur_cell_ != prev_cell)
        {
            path_stack.pop();
        }
    }
}
 
int main()
{
    std::locale::global(std::locale("rus"));
    T_path_stack  path_stack;
 
    if (!fill_stack(path_stack))
    {
        std::cout << "Нет выхода!"
            << std::endl;
    }
    else
    {
        print_path(path_stack);
    }
    system("pause");
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.06.2017, 16:49
Ответы с готовыми решениями:

Игра лабиринт. ИИ в лабиринте. Как задать лабиринт
У меня есть следующее задание: Дано: - робот - лабиринт Задание: - Нужно реализовать...

Объяснить код
Двоичный поиск #include &quot;stdafx.h&quot; #include &quot;iostream&quot; #include &quot;conio.h&quot; #include...

Объяснить код
Всем доброго времени суток. Нашел на одном сайте код: List&lt;Action&gt; actions = new List&lt;Action&gt;();...

Объяснить код
Помогите разжевать код (объяснить что делает каждая часть) т.к. я новичок в js прошу вашей помощи.

4
"C with Classes"
1642 / 1399 / 523
Регистрация: 16.08.2014
Сообщений: 5,869
Записей в блоге: 1
26.06.2017, 16:56 2
palmero, такое чувство что -1 вход, 0 коридоры, и 0 соответственно выход. в код не вникал посмотрел только на массив
C++
1
2
3
4
5
6
7
8
9
int labirint[][n] = { { 1, 1, 1, 1, 1, 0, 1, 1, 1 },
    { 1, 0, 0, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 1, 0, 0, 0, 0, 1 },
    { 1, 1, 0, 0, 0, 1, 1, 1, 1 },
    { 1, 1, 1, 1, -1, 1, 1, 1, 1 } };
1
0 / 0 / 0
Регистрация: 26.06.2017
Сообщений: 3
26.06.2017, 16:59  [ТС] 3
да, это я понял)
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
26.06.2017, 17:08 4
Цитата Сообщение от palmero Посмотреть сообщение
как эта программа устроена
Имхо не фонтан устроена - слишком много вложенных циклов.
1
0 / 0 / 0
Регистрация: 26.06.2017
Сообщений: 3
26.06.2017, 17:12  [ТС] 5
вот да, поэтому и не могу разобраться что к чему
0
26.06.2017, 17:12
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.06.2017, 17:12
Помогаю со студенческими работами здесь

Объяснить код
program l1_z6; {$APPTYPE CONSOLE} uses windows; var gg,g,x,c:integer; begin

Объяснить код
Здравствуйте, объясните , пожалуйста код я большую часть понимаю, но ,к примеру, строчка format =...

объяснить код
здравствуйте, можете объяснить код, пожалуйста? я не могу понять, как считается факториал VAR x,...

Объяснить код
Написать программу, которая вычисляет частичную сумму ряда \sum_{k=1}^{\infty}ln(1+\frac{1}{k})...

Объяснить код
Объясните пожалуйста на пальцах как заполняется объект. По сути каждый вложенный объект должен...

Объяснить код
Пожалуйста, объясните код, а то я ничего не понимаю. Если не трудно, то прям каждую строчку. За...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru