Рекурсивный поиск в глубину

@SergeyIvankov · Регистрация: 03.04.2016

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

Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину.
Фотографию примера лабиринта прикреплю.

@_Ivana · 17.09.2016, 17:30

Шо? Опять!? (С)

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
#include <iostream>
using namespace std;
 
char a[50][50];
int xm, ym;
bool solved = false;
 
void f(int i, int j) {
    if (i<0 || j<0 || i>=xm || j>=ym || solved) return;
    char c = a[i][j];
    if (c=='#' || c=='*' || c=='B') {solved = c=='B'; return;}
 
    if (c==' ') a[i][j]='*';
    f(i+1, j);
    f(i, j-1);
    f(i-1, j);
    f(i, j+1);
    if (!solved) a[i][j]=' ';
}
int main() {
    int i=0, j=0, xs, ys;
    char c;
    while (cin.get(c)) {
        if (c=='\n') {xm=i-1; i=0; j++; continue;}
        if (c=='A') {xs=i; ys=j;}
        a[i++][j]=c;
    }
    ym=j;
    f(xs, ys);
    for(int j=0; j<ym; j++) {for(int i=0; i<xm; i++) cout<<a[i][j]; cout<<'\n';}
}

http://rextester.com/YUGG19735

Code
1
2
3
4
5
6
7
8
9
10
11
12
############
#  #   # *B#
##   #   *##
#  ######**#
#  #    ##*#
# ## ##****#
#  # # *# ##
#  #  A*#  #
##   ##### #
#    #   # #
#  #   #   #
############

@SergeyIvankov · 17.09.2016, 17:46 **[ТС]**

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

@_Ivana · 17.09.2016, 17:50

А что там непонятного то? Обходим графа в глубину до первого успеха (не обязательно оптимального в каком-либо смысле, например минимального по длине), и в случае успеха трубим всем полкам отход со стека без дальнейших погружений

Новые блоги и статьи Все статьи Все блоги /
влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .

@SergeyIvankov 0 / 0 / 1 Регистрация: 03.04.2016 Сообщений: 71

	Рекурсивный поиск в глубину 17.09.2016, 16:00. Показов 2253. Ответов 3 Метки нет (Все метки) Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта прикреплю. Миниатюры 0

@SergeyIvankov 0 / 0 / 1 Регистрация: 03.04.2016 Сообщений: 71
	17.09.2016, 17:46 [ТС]
	Оо супер, огромное тебе спасибо, если будет у тебя возможность, напиши пару комментариев, что бы я сам постарался вникнуть в код. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,989 Записей в блоге: 32
	17.09.2016, 17:50
	А что там непонятного то? Обходим графа в глубину до первого успеха (не обязательно оптимального в каком-либо смысле, например минимального по длине), и в случае успеха трубим всем полкам отход со стека без дальнейших погружений 0