понять рекурсию

@jambas92 · Регистрация: 18.11.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте! Хочу понять рекурсию

для этого хочу реализовать рекурсивный выход из лабиринта. точка (.) можно ходить, решетка (#) стена, g это выход.
из начало вводится 2 цифры, это размерности символьного массива, затем вводится сам массив, затем вводится 2 цифры, это координаты начала.
например
3 3
. . .
# # .
# # g
выход есть

вот что я по пробовал сделать...

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
#include <iostream>
using namespace std;
 
bool boolean = false;
char mas[100][100];
 
int mouse(int x, int y)
{
    if (boolean == false)
    {
        if (mas[x][y] == 'G' || mas[x][y] == 'g')
        {
            boolean = true;
            return 0;
        }
        if (mas[x+1][y] == '.')
        {
            mouse(x+1, y);
        }
        if (mas[x][y+1] == '.')
        {
            mouse(x, y+1);
        }
        if (mas[x-1][y] == '.')
        {
            mouse(x-1, y);
        }
        if (mas[x][y-1] == '.')
        {
            mouse(x, y-1);
        }
    }
    else
    {
        boolean = true;
        return 0;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            cin >> mas[i][j];
        }
    }
    
    int x, y;
    cin >> x >> y;
    mouse(x,y);
 
    boolean == true ? cout << "Yes\n" : cout << "No\n";
 
    return 0;
}

в чем я ошибаюсь?

@Kuzia domovenok · 26.03.2012, 21:46

Сообщение от jambas92

Здравствуйте!
в чем я ошибаюсь?

Существуют готовые хорошие алгоритмы поиска пути. На ум приходит А*, Волновой алгоритм и.т.д.
Сам я их подзабыл уже. Вот про них погугли и на них ориентируйся.
А твоя самодеятельность похвальна , но работать на будет, просто потому что
в такой ситуации он будет ходить взад-вперёд
*****
. . И .*
*****
И -игрок
Вызов mouse в первый раз будет советовать игроку сделать шаг вправо после первой же проверки, тем самым заводя в тупик.
Следующий вызов выведет его из тупика на 1 шаг влево в прежнее положение, из которого бесконечно будет отправлять в тупик.

@jambas92 · 26.03.2012, 21:51 **[ТС]**

волновую я знаю, и как методом правой руки тоже, и самым коротким способом определить есть из лабиринта выход или нет тоже могу, просто в тех алгоритмах нет рекурсий. Как я понял в моем алгоритме не хватает возврата назад. То есть, когда есть развилка ставим метку, и идем по первому условию, если условие не удачная то возвращаемся на метку, только как это сделать?

на одном форуме нашел хороший ответ, но не могу его реализовать...

в общем объясню на словах, писать код времени нет:
как надо организовать функцию. на входе она получает 2 параметра: x; y.
первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично
если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.

@Kuzia domovenok · 26.03.2012, 22:09

если a[x+1][y] == 0 то a[x][y] = 2;

Ну и где у тебя этот момент в алгоритме? нету?
И ещё, что такое boolean? Т.е. Какую роль эта переменная играет в алгоритме?

@jambas92 · 26.03.2012, 22:20 **[ТС]**

Сообщение от Kuzia domovenok

если a[x+1][y] == 0 то a[x][y] = 2;

а куда вот его ставить та?

@Kuzia domovenok · 26.03.2012, 22:37

Сообщение от jambas92

а куда вот его ставить та?

Прочитай ещё раз:

в общем объясню на словах, писать код времени нет:
как надо организовать функцию. на входе она получает 2 параметра: x; y.
первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично
если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.

!!! если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0; !!!

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
if (mas[x+1][y] == '.')
                {
                        mas[x][y]='2';
                        mouse(x+1, y);
                        mas[x][y]='.';
                }
                if (mas[x][y+1] == '.')
                {      
                        mas[x][y]='2';
                        mouse(x, y+1);
                        mas[x][y]='.';
                }
                if (mas[x-1][y] == '.')
                {      
                        mas[x][y]='2';
                        mouse(x-1, y);
                        mas[x][y]='.';
                }
                if (mas[x][y-1] == '.')
                {
                        mas[x][y]='2';
                        mouse(x, y-1);
                        mas[x][y]='.';
                }

@jambas92 · 26.03.2012, 22:39 **[ТС]**

C++
1
2
3
4
5
6
if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='#';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

типа вот так???

@Kuzia domovenok · 26.03.2012, 22:42

Сообщение от jambas92

C++
1
2
3
4
5
6
if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='#';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

типа вот так???

Да! Да! Именно!
Только я ещё подумал, может mas[x+1][y]='#' ... mas[x+1][y]='.';
сделать общим для всех четырёх ифов?
Должно бы работать!

C++
1
2
3
4
5
6
mas[x+1][y]='#';
                if (mas[x+1][y] == '.') mouse(x+1, y);
                if (mas[x][y+1] == '.')mouse(x, y+1);
                if (mas[x-1][y] == '.') mouse(x-1, y);
                if (mas[x][y-1] == '.')  mouse(x, y-1);
mas[x+1][y]='.';

@jambas92 · 26.03.2012, 22:44 **[ТС]**

работает... прикольно

как говорится чтобы понять рекурсию нужно понять рекурсию...

@Kuzia domovenok · 26.03.2012, 22:49

Сообщение от jambas92

работает... прикольно

как говорится чтобы понять рекурсию нужно понять рекурсию...

Ну ты понял идею программы? Перед тем как пойти, скажем в правое ответвление лабиринта мы "заделываем" за собой дорогу. И так постепенно углубляемся, либо пока не оказываемся замурованными в тупике, тогда размуровываемся; шаг назад; и пробуем другое ответвление (например левое)

либо пока не найдём выход.

Вообще, отмечай дорогу не символами стен "#", а какими-нибудь специальными, например "@". Тогда когда отыщешь выход, в массиве будет "прочерчен" твой маршрут - и можно будет наглядно вывести на экран.

C++
1
2
3
4
5
6
if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='@';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

Новые блоги и статьи Все статьи Все блоги /
Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .

@jambas92 59 / 58 / 16 Регистрация: 18.11.2010 Сообщений: 315
	26.03.2012, 22:44 [ТС]
	работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию... 0