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

Узнай цену своей работы

Формулировка задачи:

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

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

textual
Листинг программы
#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;
}

Объяснение кода листинга программы

Код представляет собой функцию, использующую рекурсию, чтобы пройти лабиринт. Вот список действий, которые выполняются в коде:

  1. Ввод лабиринта:
    • Если определенный массив lab не используется ( #if (1) ), то пользователю предлагается ввести последовательность из символов 'x' и '0'.
    • В противном случае, вводится последовательность 'x0xxxxxx' и т.д., представляющая лабиринт.
  2. Инициализация переменных:
    • Массив a инициализируется введенной последовательностью.
    • Массив v инициализируется нулями, которые представляют проходные клетки.
  3. Вывод лабиринта:
    • Массив a выводится на экран, представляя лабиринт.
  4. Рекурсивный обход лабиринта:
    • Функция travel вызывается рекурсивно для обхода лабиринта.
    • Переменная ret инициализируется как 0, которая представляет успешный проход.
    • Если достигнут конец лабиринта ( b == 7 && c == 7 ), то ret становится 1.
    • Если найдена проходная клетка ( a[b+1][c] == '0' && v[b+1][c] == 0 ), то функция вызывается рекурсивно для проверки следующего хода вниз.
    • Если не найдена проходная клетка вниз и найдена проходная клетка вправо ( a[b][c+1]=='0'&& v[b][c+1] == 0 ), то функция вызывается рекурсивно для проверки следующего хода вправо.
    • Если не найдена проходная клетка вниз и влево ( c > 0 && a[b][c-1]=='0' && v[b][c-1] == 0 ), то функция вызывается рекурсивно для проверки следующего хода влево.
    • Если не найдена проходная клетка вниз и вверх ( b > 0 && a[b-1][c]=='0' && v[b-1][c] == 0 ), то функция вызывается рекурсивно для проверки следующего хода вверх.
    • Если не найдена проходная клетка в любом из направлений, то ret становится 0, что означает, что выхода нет.
  5. Вывод результата:
    • В зависимости от значения ret, выводится сообщение 'финиш' или 'выхода нет!
    • Программа ожидает нажатия клавиши pause перед завершением.
    • Возвращается 0, что означает успешное выполнение программы.

Оцени полезность:

12   голосов , оценка 4.417 из 5
Похожие ответы