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

Программу, отыскивающую проход по лабиринту - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Структуры в С++ http://www.cyberforum.ru/cpp-beginners/thread135919.html
Помогите пожалуйста!! На основе записной книжки (записывается в файл), содержащей сведения о людях (фамилия, год рождения, адрес- город, улица, дом, квартира, место работы или учебы), вывести на экран или отдельных файл по алфавиту список лиц, которые живут в доме, заданном пользователем. Начальные дааные считываеются из файла и отображаются на экране.
C++ макросы Что имеется в виду в заданиии: Создать определение макроса, который печатает имя, значение и адрес переменной типа int в следующем формате: Имя : fop; значение: 23; адрес: ff46016. Нужно #define применять? http://www.cyberforum.ru/cpp-beginners/thread135910.html
C++ Вычислить сумму элементов , pасположенных на главной диагонали и выше ее.
Дана действительная квадpатная матpица поpядка n (n<=8). Вычислить сумму тех ее элементов , pасположенных на главной диагонали и выше ее,котоpые пpевосходят по величине все элементы, pасположенные ниже главной диагонали. Если таких элементов нет , вывести на экpан соответствующее сообщение. Я понимаю, что прога не сложная, но я просто не догоняю... P.S C#.....
C++ Интернет радио
Подскажите пожалуста как организовать воспроизвидение интернет радио в програме. Есть сайт которий транслирует радио http://www.uhradio.fm Как мне принять етот поток. Добавлено через 36 минут МОжет есть функции для работи с потоком
C++ Не понятные "помехи" в FloatToStr() http://www.cyberforum.ru/cpp-beginners/thread135810.html
Кто может объяснить почему после выполнения такого кода: float b = 10.234; Edit1->Text = FloatToStr(b); в Edit1 передается не "10.234", а "10.234000205937" ?
C++ void Объясните пожалуйста как работает спецификатор тип void в функии когда он употребляется вкачестве имени типа... Добавлено через 1 минуту Объясните на примере функции input этого кода: /*Лабараторная работа № 6, Суходольский Павел, №22*/ #include <stdio.h> #include <math.h> #include <stdlib.h> подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,650
28.05.2010, 14:20     Программу, отыскивающую проход по лабиринту
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
//Написать программу, отыскивающую проход по лабиринту, с использованием 
//контейнерного класса stack из STL. Лабиринт представляется в виде матрицы, 
//состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый 
//квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, 
//но не с угла. Программа находит проход через лабиринт, двигаясь от заданного входа. 
//После отыскания прохода программа выводит найденный путь в виде координат квадратов.
#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);
    }
    return 0;
}
 
Текущее время: 16:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru