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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

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

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

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

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