[Drongo]

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

[lxa85]

Drongo,

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

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

[pva]

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

[Hardcore]

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

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


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

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

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


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

[belk94]

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

[lxa85]

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

[Hardcore]

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

[Drongo]

Найди выход из лабиринта, можно всегда если использовать правило правой руки(кажется так это называется). Тоесть, прикоснувшись правовй рукой к стене и не отрывая руки идти вперёд, если выход из лабиринта есть, то к нему выйдешь обязательно, если же пространство замкнутое\тупик, то вернёшься к тому месту, откуда начал шествие. Другими словами, нужно проверять наличие стены(#) справа, если символ равен # это стена, если же . то проход. Я решал подобную задачу года три назад, и по-дилетантски, решил только пол задачи, ту часть, где производится обход лабиринта, но часть, которая печатает по порядку путь, заменяя точки . на * решить не смог. Если кто подскажет идеей, как это сделать, думаю, сделаю, не люблю незаконченые дела оставлять. В функции 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;
    }
}
//---------------------------------------------------------------------------

[belk94]

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