Рекурсия - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Рекурсия (http://forum.oszone.net/showthread.php?t=189142)

Рекурсия

Exit form the maze

Robot is standing at the (0,0) position of the matrix maze.
Your task is to find the answer to the question - "Is it possible to find the exit from the given maze?".
Exit exists only in case you can find the way from (0,0) to (n-1,m-1) point walking only through blank places(".")
Note. Use recursion for solving this problem.

Input:
First line that contains N and M (2 <= n,m <= 6).
That matrix NxM that contain only "#" and ".".
"#" means wall(robot can not go throught the wall)
"." means blank place where robot can walk

Output:
Your output have to be contain "YES" if the exit exists and "NO" in other case.

Examples:
Input 1:
3 3
.#.
..#
#..
Output 1:
YES

Input 2:
6 5
.....
####.
.....
.###.
....#
###..
Output 2:
YES

Input 3:
3 3
.#.
..#
.#.
Output 3:
NO

Hardcore, Язык общения на конференции - русский. Правила 2.3. Озвучьте вашу задачу на русском языке.

Drongo,

Цитата:

Цитата Drongo

Озвучьте вашу задачу на русском языке. »

У ТС сложно с переводом, а машинный зачастую искажает условия задачи до неузнаваемости.
Hardcore, алгоритмов поиска пути, тем более рекурсивных, много.
Опять же не видно рассуждений, и попыток решить эту задачу самостоятельно.

вроде был такой раздел "сделайте мне лабу"

Перевод.
Вопрос задачи: наити выход роботу из лабиринта.
Робот проходит только через (.), а это (#) стенка через которые он не может пройти. Надо написать алгоритм прохода робота через лабиринт.
Условие решить через рекурсию.

Первая линия включает в себя N и M (2 <= n,m <= 6).
Это матрица NxM состайт только из "#" и ".".
"#" стены
"." проход

Пример:
Ввод:
3 3
.#.
..#
#..
Вывод
YES

Ввод 2:
6 5
.....
####.
.....
.###.
....#
###..
Вывод 2:
YES

Ввод 3:
3 3
.#.
..#
.#.
Вывод 3:
NO

Я бы начал рассуждать, но я незнаю даже с чего начать рассуждать.

Представляете лабиринт в виде графа, вершина которого - клетка, по которой можно пройти, рёбра из неё к соседним таким же клеткам. Дальше рекурсивный алгоритм обхода графа в глубину. Запускаете алгоритм из (0,0). Если (m-1,n-1) посещена - проход есть, нет - плохой лабиринт.

Hardcore, если не знаешь, с чего начать, начни с того, что знаешь. Если встретилось новое слово, рекурсия например, спроси об этот гугл, википедию и иные источники.
Ищи прям по словосочетаниям Аалгоритм, лабиринт, рекурсивный алгоритм поиска пути и т.д.
Иначе ты перед каждой новой задачей или словом будешь впадать в ступор и звать о помощи говоря "я ничего не знаю" (без обид опять таки)

Спасибо за совет. Я не обижаюсь.

Найди выход из лабиринта, можно всегда если использовать правило правой руки(кажется так это называется). Тоесть, прикоснувшись правовй рукой к стене и не отрывая руки идти вперёд, если выход из лабиринта есть, то к нему выйдешь обязательно, если же пространство замкнутое\тупик, то вернёшься к тому месту, откуда начал шествие. Другими словами, нужно проверять наличие стены(#) справа, если символ равен # это стена, если же . то проход. Я решал подобную задачу года три назад, и по-дилетантски, решил только пол задачи, ту часть, где производится обход лабиринта, но часть, которая печатает по порядку путь, заменяя точки . на * решить не смог. Если кто подскажет идеей, как это сделать, думаю, сделаю, не люблю незаконченые дела оставлять. :) В функции printSteep пытался сделать вывод каждого шага, но не получилось, сделал только вывод координат.

Код:

// Программа Прохождения лабиринта

#include <windows.h>

#include <iostream>

using namespace std;



const int row = 12;

const int column = 12;



// Функция перекодировки символов русского языка

char* Rus(const char* text);

char bufRus[256];



char* Rus(const char* text)

{

  CharToOem(text, bufRus);

  return bufRus;

}

// Функция Прохождения лабиринта

void mazeTraverse(char lab[][column], int rw, int clm, int xx, int yy, int steep);



// Печать пошагового прохождения

void printSteep(char lab[][column], int rw, int clm, int xx, int yy);



int main()

{

  char labirint[row][column] = { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                                 {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},

                                 {'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},

                                 {'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},

                                 {'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},

                                 {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},

                                 {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},

                                 {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},

                                 {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},

                                 {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},

                                 {'#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '#'},

                                 {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}  };

  int x = 2,

      y = 0,

      steep = 1,

      z;



  cout<<Rus(" Введите '0' для продолжения или '-1' для финиша :  ");

  cin>>z;

  while(z != -1){

     mazeTraverse(labirint, row, column, x, y, steep);

     cout<<Rus("\n\n Введите '0' для продолжения или '-1' для финиша :  ");

     cin>>z;

   }

  return 0;

}

// Функция прохождения лабиринта

void mazeTraverse(char lab[][column], int rw, int cl, int x, int y, int steep)

{

   printSteep(lab, rw, cl, x, y);



   if(lab[x][y] == '.' && (x == 4 && y == 11))

      return;

   // steep - 1 - движение вниз и проверка вправо на наличие стены

   else if(steep == 1){

      if(lab[x + 1][y] == '.' && lab[x + 1][y - 1] == '#'){ // вперёд - справа стена

         x++;

         steep = 1;

        }

      else if(lab[x + 1][y] == '.' && lab[x + 1][y - 1] == '.'){ // угол - поворот направо

         x++;

         steep = 2;

        }

      else if(lab[x + 1][y] == '#' && lab[x + 1][y - 1] == '#') // глухой угол - поворот налево 

         steep = 4;

     }

   // steep - 2 - движение влево и проверка вправо вверх на наличие стены

   else if(steep == 2){

      if(lab[x][y - 1] == '.' && lab[x - 1][y - 1] == '#'){

         y--;

         steep = 2;

        }

      else if(lab[x][y - 1] == '.' && lab[x - 1][y - 1] == '.'){

         y--;

         steep = 3;

        }

      else if(lab[x][y - 1] == '#' && lab[x - 1][y - 1] == '#')

         steep = 1;

     }

    // steep - 3 - движение вверх и проверка вправо вверх на наличие стены

    else if(steep == 3){

      if(lab[x - 1][y] == '.' && lab[x - 1][y + 1] == '#'){

         x--;

         steep = 3;

        }

      else if(lab[x - 1][y] == '.' && lab[x - 1][y + 1] == '.'){

         x--;

         steep = 4;

        }

      else if(lab[x - 1][y] == '#' && lab[x - 1][y + 1] == '#')

         steep = 2;

     }

    // steep - 4 - движение вправо и проверка вправо вниз на наличие стены

    else if(steep == 4){

      if(lab[x][y + 1] == '.' && lab[x + 1][y + 1] == '#'){

         y++;

         steep = 4;

        }

      else if(lab[x][y + 1] == '.' && lab[x + 1][y + 1] == '.'){

         y++;

         steep = 1;

        }

      else if(lab[x][y + 1] == '#' && lab[x + 1][y + 1] == '#')

         steep = 3;

     }

   mazeTraverse(lab, rw, cl, x, y, steep);

}

// Функция печать шага прохождения

void printSteep(char lab[][column], int rw, int cl, int x, int y)

{

   int i = 0,

       j = 0;



       cout<<endl;

       cout<<" X = "<<x<<endl;

       cout<<" Y = "<<y<<endl;



   for(i = 0; i < rw; i++){

      for(j = 0; j < cl; j++){

//         if(x != i && y != j) // Так пытался реализовать отметку шага

         cout<<lab[i][j];

  //       if(x == i && y == j) // Так пытался реализовать отметку шага

    //     cout<<'*'; // Так пытался реализовать отметку шага

        }

       cout<<endl;

    }

}

//---------------------------------------------------------------------------

Drongo, здесь не лабиринт в обычном понимании этого слова. Надо пройти из (0,0) в (m-1,n-1).