Функция, использующая рекурсию, чтобы пройти лабиринт - 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;
- }
Объяснение кода листинга программы
Код представляет собой функцию, использующую рекурсию, чтобы пройти лабиринт. Вот список действий, которые выполняются в коде:
- Ввод лабиринта:
- Если определенный массив
lab
не используется (#if (1)
), то пользователю предлагается ввести последовательность из символов'x'
и'0'
. - В противном случае, вводится последовательность
'x0xxxxxx'
и т.д., представляющая лабиринт.
- Если определенный массив
- Инициализация переменных:
- Массив
a
инициализируется введенной последовательностью. - Массив
v
инициализируется нулями, которые представляют проходные клетки.
- Массив
- Вывод лабиринта:
- Массив
a
выводится на экран, представляя лабиринт.
- Массив
- Рекурсивный обход лабиринта:
- Функция
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, что означает, что выхода нет.
- Функция
- Вывод результата:
- В зависимости от значения
ret
, выводится сообщение'финиш'
или'выхода нет!
- Программа ожидает нажатия клавиши
pause
перед завершением. - Возвращается 0, что означает успешное выполнение программы.
- В зависимости от значения
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д