Рекурсия

[Hardcore]

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

[Drongo]

Hardcore, Язык общения на конференции - русский. Правила 2.3 (http://www.forum.oszone.net/rules.html#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]

Представляете лабиринт в виде графа, вершина которого - клетка, по которой можно пройти, рёбра из неё к соседним таким же клеткам. Дальше рекурсивный алгоритм обхода графа в глубину (http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83). Запускаете алгоритм из (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).