الگوریتم چک کردن مسیر

[kooroshekabir]

سلام دوستان
من یک maze نوشتم ولی در حقیقت این تمام خونه هایی که مسیر باز داره رو ستاره دار می کنه تا مسیر رو نشون بده ولی مسیر های انحرافی تویه ماتریس هست که به بن بست م رسه.
کسی میدونه الگوریتم چک کردن خانه های ماتریس یک maze چطوریه؟؟؟
ممنون میشم کمکم کنید.

[qwerty11]

سلام دوستان
من یک maze نوشتم ولی در حقیقت این تمام خونه هایی که مسیر باز داره رو ستاره دار می کنه تا مسیر رو نشون بده ولی مسیر های انحرافی تویه ماتریس هست که به بن بست م رسه.
کسی میدونه الگوریتم چک کردن خانه های ماتریس یک maze چطوریه؟؟؟
ممنون میشم کمکم کنید.
سلام،
اولاً کدتون رو بزارین

از BFS استفاده کنین برای کوتاهترین مسیر و برای نشان دادن مسیر برای هر خونه یه فیلد parent در نظر بگیرین که خونه ایه که از اون وارد خونه ی جاری شدین. حالا از خونه ی هدف شروع کنین و با استفاده از parent خونه ها یکی یکی به عقب برگردین تا به خونه مبدا برسین

[kooroshekabir]

این هم کد

#include <iostream.h>
#include <conio.h>

int col = 1;
int row = 2;
const int ROWMAX = 11;
const int COLMAX = 17;

char maze[ROWMAX][COLMAX] =
{
{'#','#','#','#','#','#','#','#','#','#','#','#',' #','#','#','#'},
{'#','M',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','#',' ','#','#','#',' ','#'},
{'#','C',' ',' ',' ',' ',' ',' ',' ','#',' ','#',' ','#',' ','#'},
{'#','#','#','#','#','#','#','#',' ','#','#','#',' ','#',' ','#'},
{'#',' ',' ',' ',' ',' ',' ','#',' ',' ',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ',' ',' ','#',' ','#','#','#','#','#',' ','#'},
{'#',' ',' ',' ',' ',' ',' ','#',' ','#',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#',' ','#','#','#',' ','#','#','#'},
{'#',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#',' #','#','#','#'}
};

void printmaze()
{
for(int row = 0; row < ROWMAX; row++)
{
for(int col=0; col < COLMAX; col++)
cout << maze[row][col];
cout << "\n";
}
}

void runmaze(int row, int col)
{
if( (row>0 && row<ROWMAX) && (col>0 && col<COLMAX))
{
if( maze[row][col] == 'C' ) return;

if( maze[row][col] == ' ')
{

maze[row][col]='*';
runmaze(row, col+1);
runmaze(row, col-1);
runmaze(row-1, col);
runmaze(row+1, col);
}
}
}

int main()
{
clrscr();
printmaze();
cout<<"\n";
runmaze(1, 2);
printmaze();
getch();
return 0;
}

[qwerty11]

شما اول بگید این سوال کدوم درستونه ؟؟ ساختمان داده ؟ الگوریتم یا شایدم پیشرفته !؟

من صحبت از BFS کردم ولی الگوریتم شما backtrack هستش. تا حالا BFS رو پیاده سازی کردین یا نه ؟؟

[kooroshekabir]

مال درس C++‎ هستش.می خواستم تابعی بنویسم که به تویه تابع runmaze بعد از چک کردن خانه خالی اجرا بشه.

if( maze[row][col] == ' ')و اگر اون خونه خالی مسیر انحرافی داشت بره و چک کنه کنه که آیا به بن بست می خوره یا نه و اگر خورد برگرده به همون خونه ای که مسیر انحرافی داشته و یک مسیر دیگه رو چک کنه ولی من زیاد C++‎ بلد نیستم می خواستم ببینم می تونید کمکم کنید؟؟؟