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

Какими методами лучше реализовать генерацию и поиск выхода из лабиринта?

01.06.2019, 19:50. Показов 481. Ответов 4

Нужно сделать генерацию рандомнго лабиринта, и поиск выхода с него на С++. Подскажите пожалуйста как это сделать. Может у вас уже есть готовая реализация программы. Буду очень благодарен
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.06.2019, 19:50
Ответы с готовыми решениями:

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. Общий...

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.

Программа «поиск выхода из лабиринта»
Открывать файл «карту», имя файла передавать как параметр командной строки. Считать, что в карте...

Исправить поиск выхода из лабиринта
Есть программа поиска выхода из лабиринта: #include <stdio.h> #include <io.h> #include...

4
1500 / 964 / 811
Регистрация: 30.04.2016
Сообщений: 3,333
02.06.2019, 21:05 2
vladik42851, здравствуйте! Генерации я не делал, но сталкивался с поиском выхода. Для этого удобно использовать рекурсию с возвратом. Если вам нужно, я могу скинуть разобранный код с комментариями. Я когда-то его разбирал.
0
0 / 0 / 0
Регистрация: 24.01.2019
Сообщений: 103
05.06.2019, 17:39  [ТС] 3
Fixer_84, здравствуйте, если можно скиньте пожалуйста
0
106 / 82 / 15
Регистрация: 07.06.2011
Сообщений: 582
Записей в блоге: 2
05.06.2019, 17:42 4
По моему тут проще использовать волновой метод прохождения лабиринтов. Погуглите. Построить лабиринт - ну начните с какого-нибудь простого шаблона, больше не могу подсказать.
0
1500 / 964 / 811
Регистрация: 30.04.2016
Сообщений: 3,333
06.06.2019, 22:11 5
vladik42851, вот код с комментариями. Правда, тут есть ограничения. Выход (не начало) обязательно должен быть в правом нижнем углу.

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
#include <bits/stdc++.h> //Подключаем весь набор заголовочных файлов (можно заменить на только необходимые)
#define SIZE 7 //Размер матрицы (лабиринта)
 
    using namespace std;
 
int maze[SIZE][SIZE] = { //Исходная матрица (лабиринт)
    {1, 1, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 1, 1},
    {1, 0, 0, 1, 0, 1, 1},
    {1, 1, 1, 1, 0, 0, 1},
    {1, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 0, 0},
};
 
int solution[SIZE][SIZE]; //Матрица для хранения решения (матрица ходов)
 
void printsolution() { //Функция вывода результата
    int i, j;
    for(i = 0; i < SIZE; i++) {
        for(j = 0; j < SIZE; j++) {
            printf("%d",solution[i][j]);
        }
        printf("\n");
    }
}
 
//Функция решающая лабиринт, используя поиск с возвратом (recursive backtracking)
int solvemaze(int r, int c) {
    if((r == SIZE - 1) && (c == SIZE - 1)) { //Если правый нижний угол достигнут (база рекурсии)
        solution[r][c] = 1;
        return 1;
    }
    //Проверка можем ли мы попасть в клетку (индексы должны быть от 0 до SIZE - 1)
    //Условие solution[r][c] == 0 - то есть, клетка в матрице ходов не занята (изначально матрица ходов заполнена нулями)
    //Условие maze[r][c] == 0 гарантирует, что клетка в исходной матрице (лабиринте) не блокирована (то есть, может быть посещена)
    if(r >= 0 && c >= 0 && r < SIZE && c < SIZE && solution[r][c] == 0 && maze[r][c] == 0) {
        solution[r][c] = 1; //Установка хода (если ход можно сделать)
        if(solvemaze(r + 1, c))  //Ход вниз
            return 1;
        if(solvemaze(r, c + 1))  //Ход вправо
            return 1;
        if(solvemaze(r - 1, c))  //Ход вверх
            return 1;
        if(solvemaze(r, c - 1))  //Ход влево
            return 1;
        solution[r][c] = 0; //Возврат назад (backtracking), то есть, ход сделать нельзя
        return 0;
    }
    return 0;
 
}
 
int main() {
    int i, j;
    for(i = 0; i < SIZE; i++) {
        for(j = 0; j < SIZE; j++) {
            solution[i][j] = 0; //Обнуляем матрицу ходов
        }
    }
    if (solvemaze(1, 0)) //Координаты начала лабиринта
        printsolution();
    else
        printf("No solution\n");
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.06.2019, 22:11
Помогаю со студенческими работами здесь

Поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл
Нужно провести поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл...

Поиск выхода из лабиринта
Необходимо реализовать поиск выхода из лабиринта вот допустим лабиринт,но тут он выводит только...

Поиск выхода из лабиринта
Здравствуйте! Изучаю C#, застрял на одном моменте в задании. Суть такова: нужно найти выход из...

Поиск выхода из лабиринта
Доброго времени суток! Помогите написать процедуру использующую стек для отыскания прохода по...


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

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

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