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

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

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

Помогите пожалуйста найти и исправить ошибку. Есть задача :" Напишите функцию,которая получает массив символов 8х8, представляющих собой лабиринт.Найдите хотя бы один путь через него, с началом в точке (0,1) и концом в точке(7,7), с помощью рекурсии! Если пути не существует ,то выведите соответствующее сообщение. После заупска и ввода лабиринта зацикливается на: Вправо Вправо Вправо....
Листинг программы
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. void
  4. travel(const char a[][8]);
  5. int
  6. main(void)
  7. {
  8. int i,j;
  9. char a[8][8];
  10. printf("Введите последовательность из х и 0>");
  11. for(i=0;i<8;i++)
  12. {
  13. for(j=0;j<8;j++)
  14. scanf ("%c",&a[i][j]);
  15. }
  16. printf("\n");
  17. for(i=0;i<8;i++)
  18. {
  19. for(j=0;j<8;j++)
  20. printf("%c",a[i][j]);
  21. printf("\n");
  22. }
  23. travel(a);
  24. system ("pause");
  25. return 0;
  26. }
  27.  
  28. void
  29. travel(const char a[][8])
  30. {
  31. int b=0,c=1;
  32. if ((b==7) && (c==7))
  33. printf ("Финиш");
  34. else
  35. {
  36. if(a[b][c+1]=='0')
  37. {
  38. printf ("Вправо\n");
  39. c=c+1;
  40. travel (a);
  41. }
  42. else
  43. {
  44. if(a[b+1][c]=='0')
  45. {
  46. printf("Вниз\n");
  47. b=b+1;
  48. travel(a);
  49. }
  50. else
  51. {
  52. if(a[b][c-1]=='0')
  53. {
  54. printf ("Влево\n");
  55. c=c-1;
  56. travel(a);
  57. }
  58. else
  59. {
  60. if(a[b-1][c]=='0')
  61. {
  62. printf ("Вверх\n");
  63. b=b-1;
  64. travel(a);
  65. }
  66. else
  67. printf ("Пути нет");
  68. }
  69. }
  70. }
  71. }
  72. }

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

textual
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <locale.h>
  5.  
  6. int
  7. travel(const char a[][8], int b, int c, int v[][8]);
  8.  
  9. int
  10. main(void)
  11. {
  12.     int i,j;
  13.     char a[8][8];
  14.     int v[8][8];
  15.  
  16.     setlocale(LC_ALL, "Russian");
  17.  
  18. #if (1)
  19.     // если лень вводить каждый раз
  20.     char lab[] =
  21.     "x0xxxxxx"
  22.     "x0xx000x"
  23.     "x0xx0x0x"
  24.     "x0000x0x"
  25.     "x0xx0x0x"
  26.     "x0000x0x"
  27.     "x0xxxx00"
  28.     "x0xxxxx0";
  29.     memcpy(a, lab, sizeof(a));
  30.  
  31. #else
  32.     printf("Введите последовательность из х и 0>");
  33.    
  34.     for(i=0;i<8;i++)
  35.     {
  36.        for(j=0;j<8;j++)
  37.          scanf ("%c",&a[i][j]);
  38.     }
  39. #endif
  40.    
  41.     printf("\n");
  42.    
  43.     for(i=0;i<8;i++)
  44.     {
  45.         for(j=0;j<8;j++)
  46.             printf("%c",a[i][j]);
  47.         printf("\n");
  48.     }
  49.  
  50.     memset(v, 0, sizeof(v));
  51.     printf("%s\n", travel(a, 0, 1, v) ? "финиш" : "выхода нет!" );
  52.  
  53.     system ("pause");
  54.     return 0;
  55. }
  56.  
  57. int travel(const char a[][8], int b, int c, int v[][8]) {
  58.     int ret = 0;
  59.     v[b][c] = 1;
  60.     if (b == 7 && c == 7) return 1;
  61.     if (b < 7 && a[b+1][c] == '0' && v[b+1][c] == 0) {
  62.         printf("вниз %d:%d\n", b+1, c);
  63.         ret = travel(a, b + 1, c, v);
  64.         if (!ret) printf("возврат %d:%d\n", b, c);
  65.     }
  66.     if (!ret && c < 7 && a[b][c+1]=='0'&& v[b][c+1] == 0) {
  67.         printf ("вправо %d:%d\n", b, c+1);
  68.         ret = travel(a, b, c+1, v);
  69.         if (!ret) printf("возврат %d:%d\n", b, c);
  70.     }
  71.     if (!ret && c > 0 && a[b][c-1]=='0' && v[b][c-1] == 0) {
  72.         printf ("влево %d:%d\n", b, c-1);
  73.         ret = travel(a, b, c-1, v);
  74.         if (!ret) printf("возврат %d:%d\n", b, c);
  75.     }
  76.     if (!ret && b > 0 && a[b-1][c]=='0' && v[b-1][c] == 0) {
  77.         printf ("вверх %d:%d\n", b-1, c);
  78.         ret = travel(a, b-1, c, v);
  79.         if (!ret) printf("возврат %d:%d\n", b, c);
  80.     }
  81.     return ret;
  82. }

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

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

  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

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы