Лабиринт - всички пътища

[justme.h]

Здравейте, имам да реша следната задача:

Чрез една таблица от n x n клетки е представен лабиринт, като по подходящ начин част от клетките са представени като проходими, а останалите като непроходими. В една от проходимите клетки с адрес (xin,yin) има мишле, а в друга такава клетка с адрес (xfin,yfin) има сиренце. Напишете програма, която генерира всички преки пътища, по които мишлето може да стигне до сиренцето?

Моля за помощ, дори и да не е решение, някой ако може да даде насоки как да я реша.
Благодаря предварително!

[Davids]

Звучи ми като задача за deep search алгоритъм. Само думичката "преки" ми е леко объркваща в условието - търсим всички пътища или най-прекия (или най-преките, ако има няколко с еднаква дължина)? Какъвто и да е случаят, идеята е следната:
- започваш от стартовата клетка. Създаваш метод за клетка, който да ти връща всички проходими съседни клетки, към които мишката може да се придвижи.
- създаваш рекурсивен метод, който буквално мести мишката по веднъж във всяка съседна клетка и го викаш отново със стартова клетка - новата клетка. Важното е тук, за всеки рекурсивен клон от този метод да пазиш пътечката досега. И остава финалът - ако методът стигне сиренцето, значи пътят е успешен и запазваш поредицата от клетки; ако стигнеш крайна клетка, в която не е сиренцето и няма накъде да мърдаш (без да обхождаш вече минати клетки), значи терминираш рекурсивния клон и пътечката не ти върши работа.

Накрая вече ще си си събрал всички възможни пътечки. И можеш да решиш какво да си правиш с тях.

[justme.h]

Звучи ми като задача за deep search алгоритъм. Само думичката "преки" ми е леко объркваща в условието - търсим всички пътища или най-прекия (или най-преките, ако има няколко с еднаква дължина)? Какъвто и да е случаят, идеята е следната:
- започваш от стартовата клетка. Създаваш метод за клетка, който да ти връща всички проходими съседни клетки, към които мишката може да се придвижи.
- създаваш рекурсивен метод, който буквално мести мишката по веднъж във всяка съседна клетка и го викаш отново със стартова клетка - новата клетка. Важното е тук, за всеки рекурсивен клон от този метод да пазиш пътечката досега. И остава финалът - ако методът стигне сиренцето, значи пътят е успешен и запазваш поредицата от клетки; ако стигнеш крайна клетка, в която не е сиренцето и няма накъде да мърдаш (без да обхождаш вече минати клетки), значи терминираш рекурсивния клон и пътечката не ти върши работа.

Накрая вече ще си си събрал всички възможни пътечки. И можеш да решиш какво да си правиш с тях.

Нешо такова ли трябва да стане:
#include <iostream>
using namespace std;

const int SIZE = 7;
char lab[][SIZE] = {
{' ',' ',' ','#',' ',' ',' '},
{' ',' ','#','#',' ',' ',' '},
{' ',' ',' ',' ',' ',' ',' '},
{' ',' ',' ',' ',' ',' ',' '},
{' ',' ','#',' ','#',' ',' '},
{' ',' ',' ',' ',' ',' ',' '},
{' ',' ',' ',' ',' ','c',' '}
};

char* path = new char[SIZE*SIZE];
int position = 0;

void printPath(char* path, int start, int end)
{
cout << "Found path to the cheese: ";
for (int i = start; i <= end; i++)
{
cout << path[i] << " ";
}
cout << endl;
}
void findPath(int row, int col,char direction)
{
if(col<0 || row<0 || col >= SIZE || row>=SIZE)
{
return;
}

path[position] = direction;
position++;

if (lab[row][col] == 'c')
{
printPath(path, 1, position - 1);
}

if (lab[row][col] != ' ')
{
return;
}

if (lab[row][col] == ' ')
{
lab[row][col] = 'v';

findPath(row, col - 1,'L'); //left
findPath(row - 1, col,'U'); //up
findPath(row, col + 1,'R'); //right
findPath(row + 1, col,'D'); //down

//lab[row][col] = ' ';
}

position--;
}


int main()
{
findPath(0,0,'S');
system("pause");
}