Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Vehicle
2 / 2 / 1
Регистрация: 21.03.2015
Сообщений: 6
#1

Прохождение лабиринта

21.03.2015, 18:50. Просмотров 1492. Ответов 9
Метки нет (Все метки)

Как написать программу для прохождения лабиринта? У меня не получается.
Саму программу можно не писать, а только алгоритм дайте и советы.
Я уже пробовал решать. Пытался проверять все возможные комбинации. Из-за этого программа быстро увеличивается в размерах.
Лабиринт это двумерный массив board[12][12]. Пустая клетка обозначается 0, стены 1, а те клетки где уже побывал - 2.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.03.2015, 18:50
Ответы с готовыми решениями:

Прохождение лабиринта
Приведенная ниже сетка единиц и нулей - двумерный массив, представляющий...

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

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

Прохождение лабиринта
Всем привет! Преподаватель по ОАиП дал задание. Учусь на специальность не...

Прохождение лабиринта
Имеется лабиринт. Нужно составить алгоритм, по которому программа найдет...

9
MicM
824 / 483 / 324
Регистрация: 29.12.2009
Сообщений: 1,106
Завершенные тесты: 1
21.03.2015, 18:52 #2
В смысле, найти выход из лабиринта?
0
Vehicle
2 / 2 / 1
Регистрация: 21.03.2015
Сообщений: 6
21.03.2015, 18:56  [ТС] #3
Да, нужно найти выход из лабиринта. Сначала задаются начальные координаты. Нужно передвигаться по лабиринту
вдоль правой стены. Т.е. правой рукой держаться за стену и двигаться. Таким способом будет найден выход
0
nonedark2008
1035 / 773 / 215
Регистрация: 28.07.2012
Сообщений: 2,153
21.03.2015, 19:01 #4
Цитата Сообщение от Vehicle Посмотреть сообщение
Пытался проверять все возможные комбинации.
1. Массив с пометками пройденных клеток
2. Рекурсия =)
1
SmittWesson
211 / 184 / 21
Регистрация: 04.06.2014
Сообщений: 1,306
21.03.2015, 19:02 #5
Алгоритм мыши Шенона.
1
Vehicle
2 / 2 / 1
Регистрация: 21.03.2015
Сообщений: 6
21.03.2015, 19:10  [ТС] #6
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Рекурсия =)
А можно без рекурсии? Или это сложно получится?

Добавлено через 6 минут
Всем спасибо. Я нашел сайт где объясняется прохождение лабиринта
http://myrobot.ru/articles/logo_mazesolving.php
0
nonedark2008
1035 / 773 / 215
Регистрация: 28.07.2012
Сообщений: 2,153
21.03.2015, 19:14 #7
Цитата Сообщение от Vehicle Посмотреть сообщение
Я нашел сайт где объясняется прохождение лабиринта
Там также написано, что он подходит не для всех лабиринтов.
Цитата Сообщение от Vehicle Посмотреть сообщение
А можно без рекурсии? Или это сложно получится?
Можно эмулировать рекурсию через стек, т.е. заносить в стек те маршруты,
по которым необходимо пройти, если по текущему мы не найдем выход.
1
ValeryS
Модератор
7211 / 5474 / 681
Регистрация: 14.02.2011
Сообщений: 18,515
21.03.2015, 19:21 #8
волновой алгоритм
1
MicM
824 / 483 / 324
Регистрация: 29.12.2009
Сообщений: 1,106
Завершенные тесты: 1
21.03.2015, 19:36 #9
Лучший ответ Сообщение было отмечено Vehicle как решение

Решение

Могу предложить такой вариант
-1 препятствие
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
#include <iostream>
#include <iomanip>
 
void labyrinth (int board[6][6], int x, int y, int k)
{
    board[x][y] = k;
    if (x > 0 && !board[x - 1][y])
        labyrinth(board, x - 1, y, k + 1);
    if (y < 5 && !board[x][y + 1])
        labyrinth(board, x, y + 1, k + 1);
    if (x < 5 && !board[x + 1][y])
        labyrinth(board, x + 1, y, k + 1);
    if (y > 0 && !board[x][y - 1])
        labyrinth(board, x, y - 1, k + 1);
}
 
int main()
{
    int board[6][6] =
    {
        {-1,-1,0,-1,-1,-1},
        {-1,0,0,-1,0,-1},
        {-1,0,-1,-1,0,-1},
        {-1,0,0,0,0,-1},
        {-1,0,-1,0,-1,-1},
        {-1,-1,-1,-1,-1,-1}
    };
    int x = 3, y = 3;
    std::cout <<"Start: (" <<x <<',' <<y <<")\n";
    labyrinth(board, x, y, 1);
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            std::cout <<std::setw(3) <<board[i][j];
        }
        std::cout <<std::endl;
    }
}
1
SorryImNotDaddy
0 / 0 / 1
Регистрация: 14.01.2015
Сообщений: 6
20.05.2015, 13:34 #10
Цитата Сообщение от MicM Посмотреть сообщение
(y > 0 && !board[x][y - 1])
Что означает это условие?
0
20.05.2015, 13:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2015, 13:34

Прохождение лабиринта
Нужно пройти от 1 до 16 самым коротким путем. И вывести на экран количество...

Прохождение лабиринта со стеком
Добрый вечер После запуска программа вылетает с ошибкой Stack Overflow и...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru