Функция, использующая рекурсию, чтобы пройти лабиринт

@katyalaym · Регистрация: 15.06.2014

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

Помогите пожалуйста найти и исправить ошибку.
Есть задача :" Напишите функцию,которая получает массив символов 8х8, представляющих собой лабиринт.Найдите хотя бы один путь через него, с началом в точке (0,1) и концом в точке(7,7), с помощью рекурсии! Если пути не существует ,то выведите соответствующее сообщение.

После заупска и ввода лабиринта зацикливается на:
Вправо
Вправо
Вправо....

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<stdio.h>
#include<stdlib.h>
 
void 
travel(const  char a[][8]);
 
int 
main(void)
{   
    int i,j;
    char a[8][8];
    
    printf("Введите последовательность из х и 0>");
    
    for(i=0;i<8;i++)
    {
       for(j=0;j<8;j++)
         scanf ("%c",&a[i][j]);
    }
    
    printf("\n");
    
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
            printf("%c",a[i][j]);
        printf("\n");
    }
    
    travel(a);
 
    system ("pause");
    return 0;
}
 
 
void
travel(const char a[][8])
{
    int b=0,c=1;
    
    if ((b==7) && (c==7))
     printf ("Финиш");
    else
    {
        if(a[b][c+1]=='0')
        {
           printf ("Вправо\n");
           c=c+1;
           travel (a);         
        }
        else
        {
             if(a[b+1][c]=='0')
             {
                printf("Вниз\n");
                b=b+1;
                travel(a);
             }
             else
             {
                 if(a[b][c-1]=='0')
                 {
                   printf ("Влево\n");
                   c=c-1;
                   travel(a);
                 }
                 else 
                 {
                     if(a[b-1][c]=='0')
                     {
                            printf ("Вверх\n");
                            b=b-1;
                            travel(a);
                     }
                     else
                      printf ("Пути нет");
                 }
             }
        }
    }
}

@schdub · 16.06.2014, 02:13

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

C
1
2
int b=0,c=1;
if ((b==7) && (c==7))

Это условие никогда не выполнится, т.к. строчкой выше вы приравняли значение переменных b и с

katyalaym, нужен дополнительный массив (v), чтобы исключить циклы

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
//...
 
int travel(const char a[][8], int b, int c, int v[][8]) {
    int ret = 0;
    v[ b ][ c ] = 1;
    if (b == 7 && c == 7) return 1;
    if (b < 7 && a[b+1][ c ] == '0' && v[b+1][ c ] == 0) {
        printf("вниз %d:%d\n", b+1, c);
        ret = travel(a, b + 1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c < 7 && a[b][c+1]=='0'&& v[b][c+1] == 0) {
        printf ("вправо %d:%d\n", b, c+1);
        ret = travel(a, b, c+1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c > 0 && a[b][c-1]=='0' && v[b][c-1] == 0) {
        printf ("влево %d:%d\n", b, c-1);
        ret = travel(a, b, c-1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && b > 0 && a[b-1][ c ]=='0' && v[b-1][ c ] == 0) {
        printf ("вверх %d:%d\n", b-1, c);
        ret = travel(a, b-1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    return ret;
}
 
//...

Code
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
x0xxxxxx
x0xx000x
x0xx0x0x
x0000x0x
x0xx0x0x
x0000x0x
x0xxxx00
x0xxxxx0
вниз 1:1
вниз 2:1
вниз 3:1
вниз 4:1
вниз 5:1
вниз 6:1
вниз 7:1
возврат 6:1
возврат 5:1
вправо 5:2
вправо 5:3
вправо 5:4
вверх 4:4
вверх 3:4
влево 3:3
влево 3:2
возврат 3:3
возврат 3:4
вверх 2:4
вверх 1:4
вправо 1:5
вправо 1:6
вниз 2:6
вниз 3:6
вниз 4:6
вниз 5:6
вниз 6:6
вправо 6:7
вниз 7:7
финиш

@katyalaym · 16.06.2014, 12:59 **[ТС]**

а что означает строка?

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

if (!ret)

Добавлено через 1 минуту
теперь у меня зацикливается на вниз вниз вниз

Добавлено через 5 минут

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
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<stdlib.h>
 
int
travel(const  char a[][8],int b,int c,int v[][8]);
 
int 
main(void)
{   
    int i,j,b=0,c=1,v[8][8];
    char a[8][8];
    
    printf("Ââåäèòå ïîñëåäîâàòåëüíîñòü èç õ è 0>");
    
    for(i=0;i<8;i++)
    {
       for(j=0;j<8;j++)
         scanf ("%c",&a[i][j]);
    }
    
    printf("\n");
    
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
            printf("%c",a[i][j]);
        printf("\n");
    }
    
    travel(a,b,c,v);
 
    system ("pause");
    return 0;
}
 
int
travel(const char a[][8], int b, int c, int v[][8])
{
    int ret = 0;
    v[b][ c] = 1;
    
    if (b == 7 && c == 7) 
    {  
       return 1;
       printf("Ôèíèø");
    }
    if (b < 7 && a[b+1][ c ] == '0' && v[b+1][ c ] == 0)
    {
        printf("âíèç %d:%d\n", b+1, c);
        ret = travel(a, b+1, c, v);
        if (!ret) 
         printf("âîçâðàò %d:%d\n", b, c);
    }
    if (!ret && c < 7 && a[b][c+1]=='0'&& v[b][c+1] == 0)
    {
        printf ("âïðàâî %d:%d\n", b, c+1);
        ret = travel(a, b, c+1, v);
        if (!ret)
           printf("âîçâðàò %d:%d\n", b, c);
    }
    if (!ret && c > 0 && a[b][c-1]=='0' && v[b][c-1] == 0) 
    {
        printf ("âëåâî %d:%d\n", b, c-1);
        ret = travel(a, b, c-1, v);
        if (!ret) 
           printf("âîçâðàò %d:%d\n", b, c);
    }
    if (!ret && b > 0 && a[b-1][ c ]=='0' && v[b-1][ c ] == 0) 
    {
        printf ("ââåðõ %d:%d\n", b-1, c);
        ret = travel(a, b-1, c, v);
        if (!ret) 
           printf("âîçâðàò %d:%d\n", b, c);
    }
    return ret;
}

@schdub · 16.06.2014, 13:36

katyalaym,

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>
 
int 
travel(const char a[][8], int b, int c, int v[][8]);
 
int 
main(void)
{
    int i,j;
    char a[8][8];
    int v[8][8];
 
    setlocale(LC_ALL, "Russian");
 
#if (1)
    // если лень вводить каждый раз
    char lab[] =
    "x0xxxxxx"
    "x0xx000x"
    "x0xx0x0x"
    "x0000x0x"
    "x0xx0x0x"
    "x0000x0x"
    "x0xxxx00"
    "x0xxxxx0";
    memcpy(a, lab, sizeof(a));
 
#else
    printf("Введите последовательность из х и 0>");
    
    for(i=0;i<8;i++)
    {
       for(j=0;j<8;j++)
         scanf ("%c",&a[i][j]);
    }
#endif
    
    printf("\n");
    
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
            printf("%c",a[i][j]);
        printf("\n");
    }
 
    memset(v, 0, sizeof(v));
    printf("%s\n", travel(a, 0, 1, v) ? "финиш" : "выхода нет!" );
 
    system ("pause");
    return 0;
}
 
int travel(const char a[][8], int b, int c, int v[][8]) {
    int ret = 0;
    v[b][c] = 1;
    if (b == 7 && c == 7) return 1;
    if (b < 7 && a[b+1][c] == '0' && v[b+1][c] == 0) {
        printf("вниз %d:%d\n", b+1, c);
        ret = travel(a, b + 1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c < 7 && a[b][c+1]=='0'&& v[b][c+1] == 0) {
        printf ("вправо %d:%d\n", b, c+1);
        ret = travel(a, b, c+1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c > 0 && a[b][c-1]=='0' && v[b][c-1] == 0) {
        printf ("влево %d:%d\n", b, c-1);
        ret = travel(a, b, c-1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && b > 0 && a[b-1][c]=='0' && v[b-1][c] == 0) {
        printf ("вверх %d:%d\n", b-1, c);
        ret = travel(a, b-1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    return ret;
}

@katyalaym · 16.06.2014, 22:44 **[ТС]**

урааа

все работает)
спасибо огромное

Добавлено через 4 часа 47 минут
schdub, Если не сложно объясните пожалуйста как работают , и что это такое, строки -18,31,39,51. Или где можно почитать об этом?
С таким не сталкивалась, а объяснить в отчете что это -нужно.

@schdub · 17.06.2014, 09:18

katyalaym, это дерективы препроцессора для условной компляции, работает как if в коде, только на уровне компилятора. Используется для быстрого включения/отключения блока кода:

C
1
2
3
4
5
#if (1)
    printf("Этой строка будет выполнена");
#else
    printf("Этой строка НЕ будет выполнена");
#endif

Если мы изменем 1 на 0, то при выполнении данного примера будет выполнен 2-ой printf() вместо 1-го.

Здесь это используется чтобы не вводить при каждом запуске программы 64 символа, мы копируем их из строки lab. Используется для целей отладки. Ну а вам, наверное, этот блок кода вообще лучше не упоминать:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>
 
int travel(const char a[][8], int b, int c, int v[][8]);
 
int main() {
    int i, j;
    char a[8][8];
    int  v[8][8];
 
    setlocale(LC_ALL, "Russian");
 
    printf("Введите последовательность из х и 0>");
 
    for (i = 0; i < 8; ++i) {
       for (j = 0; j < 8; ++j)
         scanf("%c", &a[i][j]);
    }
 
    printf("\n");
    
    for (i = 0; i < 8; ++i) {
        for (j = 0; j < 8; ++j)
            printf("%c", a[i][j]);
        printf("\n");
    }
 
    memset(v, 0, sizeof(v));
    printf("%s\n", travel(a, 0, 1, v) ? "финиш" : "выхода нет!" );
 
    system ("pause");
    return 0;
}
 
int travel(const char a[][8], int b, int c, int v[][8]) {
    int ret = 0;
    v[ b ][ c ] = 1;
    if (b == 7 && c == 7) return 1;
    if (b < 7 && a[b+1][ c ] == '0' && v[b+1][ c ] == 0) {
        printf("вниз %d:%d\n", b+1, c);
        ret = travel(a, b + 1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c < 7 && a[ b ][c+1]=='0'&& v[ b ][c+1] == 0) {
        printf ("вправо %d:%d\n", b, c+1);
        ret = travel(a, b, c+1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && c > 0 && a[ b ][c-1]=='0' && v[ b ][c-1] == 0) {
        printf ("влево %d:%d\n", b, c-1);
        ret = travel(a, b, c-1, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    if (!ret && b > 0 && a[b-1][ c ]=='0' && v[b-1][ c ] == 0) {
        printf ("вверх %d:%d\n", b-1, c);
        ret = travel(a, b-1, c, v);
        if (!ret) printf("возврат %d:%d\n", b, c);
    }
    return ret;
}

насчет строки 51 из сообщения #4, то это тернарная условная операция. Сокращенный аналог вот этого кода:

C
1
2
3
4
5
if (travel(a, 0, 1, v)) {
    printf("финиш");
} else {
    printf("выхода нет!");
}

@katyalaym · 22.06.2014, 18:15 **[ТС]**

schdub, ооо классно

мне все засчитали,
еще раз спасибо))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии 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(), которая. . .

@katyalaym 0 / 0 / 0 Регистрация: 15.06.2014 Сообщений: 5
	16.06.2014, 22:44 [ТС]
	урааа все работает) спасибо огромное Добавлено через 4 часа 47 минут schdub, Если не сложно объясните пожалуйста как работают , и что это такое, строки -18,31,39,51. Или где можно почитать об этом? С таким не сталкивалась, а объяснить в отчете что это -нужно. 0

@katyalaym 0 / 0 / 0 Регистрация: 15.06.2014 Сообщений: 5
	22.06.2014, 18:15 [ТС]
	schdub, ооо классно мне все засчитали, еще раз спасибо)) 0

Функция, использующая рекурсию, чтобы пройти лабиринт

Решение