یک کم کوچیک واسه تکمیل برنامم

[kooroshekabir]

سلام دوستان این کد برنامه maze رو به صورت خیلی معمولی چاپ می کنه.می خواستم ببینم می تونید کمک کنید که خونه هایی که پیدا می کنه اندیسش رو بریزه تویه پشته و در آخر کوتاه ترین مسیر رو از پشته پاپ کنه؟؟؟
ممنون میشم اگه کمکم کنید.

#include <iostream.h>
#include <conio.h>
//using namespace std;

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

char maze[ROWMAX][COLMAX] =
{
{'B','B','B','B','B','B','B','B','B','B','B','B',' B','B','B','B'},
{'B','M',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','B'},
{'B','B','B','B','B','B','B','B','B','B',' ','B','B','B',' ','B'},
{'B','W',' ',' ',' ',' ',' ',' ',' ','B',' ','B',' ','B',' ','B'},
{'B','B','B','B','B','B','B','B',' ','B','B','B',' ','B',' ','B'},
{'B',' ',' ',' ',' ',' ',' ','B',' ',' ',' ',' ',' ','B',' ','B'},
{'B','B','B','B','B','B','B','B',' ','B','B','B','B','B',' ','B'},
{'B',' ',' ',' ','B',' ',' ',' ',' ','B',' ',' ',' ',' ',' ','B'},
{'B',' ',' ',' ',' ',' ',' ',' ','B','B','B','B',' ','B','B','B'},
{'B',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','B'},
{'B','B','B','B','B','B','B','B','B','B','B','B',' B','B','B','B'}
};
void printMaze();
void runMaze(int, int);


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] == 'W' ) 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();
cout << "Maze before solution:\n";
printMaze();
cout << "Maze after solution:\n";
runMaze(1, 2);
printMaze();
getch();
return 0;
}

[qwerty11]

سلام،

با پشته مطمئن نیستم بشه ! اما میشه یه فیلد parent واسه عناصر جدول در نظر بگیری و در آخر مسیر رو از آخر به اول بیای طی کنی.

ضمن اینکه این چیزی که شما نوشتی صرفاً کوتاهترین مسیر رو پیدا نمیکنه و برای پیدا کردن کوتاهترین مسیر ممکن باید از صف استفاده کنید. این چیزی که شما نوشتی صرفاً مشخص میکنه که خونه ی نهایی ما reachable هست یا نه.

[kooroshekabir]

خب من هم می خوام که مسیر رو تویه پشته بریزه و اگر به دیوار خورد و به انتها نرسیده بود اون مسیر اضافه رو از پشته حذف کنه.
می خواستم ببینم این امکان پذیر هستش؟؟؟

[qwerty11]

خب من هم می خوام که مسیر رو تویه پشته بریزه و اگر به دیوار خورد و به انتها نرسیده بود اون مسیر اضافه رو از پشته حذف کنه.
می خواستم ببینم این امکان پذیر هستش؟؟؟

میشه ولی دیگه لزوماً کوتاهترین مسیر نمیشه، مگر اینکه همه ی مسیرهای ممکن رو پیمایش کنی و کوچکترین مسیری که به خونه ی هدف میره رو در نظر بگیری.

این حرفایی که از الآن میگم واسه حالتیه که فقط به دست آوردن جواب مهمه و نه بهینه ترینش.

2 تا کار میتونی در نظر بگیری :

1- خروجی تابع runmaze رو bool در نظر بگیر، حالا این قسمتی که تو تابع runmaze توابع runmaze دیگه ای رو صدا میزنی یه if قبلشون بزار که اگه خروجیشون true بود چاپ کنه اون خونه رو و return کنه true رو. ببخشید چون امکانات اینجا خیلی کمه و خیلی هم ضعیفه نمیتونم با کد نشونت بدم .

2- تو تابع runmaze هر وقت توابعی از نوع runmaze رو صدا میزنی مقدارهای x,y اونا رو تو یه stack عمومی push کن و هر وقت به انتهای تابع runmaze رسیدی از استک pop کن. و اون خط اول تابع runmaze هم اینو اضافه کن که اگه خونه ی نهایی بود بیاد مقادیر درون stack رو نشون بده.

امیدوارم کمکت کرده باشن ...

[kooroshekabir]

منمنون عزیز
فقط اون قسمتی که در مورد IF تویه تابع runmaze گفتی درست متوجه نشدم.اگر ممکنه یک کد واسم بزاری یا یکم واضحتر بگی ممنون میشم.
ممنون.

[qwerty11]

bool runmaze (int row,int col){
if( row==-1 || row==ROWMAX || col==-1 || col==COLMAX ) return false;

stack.push(pair(row,col));

if(maze[row][col] == 'W'){
//cout<<stack;
return true;
}
if( runMaze(row, col+1) ) return true;
if( runMaze(row, col-1) ) return true;
if( runMaze(row-1, col) ) return true;
if( runMaze(row+1, col) ) return true;

stack.pop();

return false;
}



منظور از چاپ کردن stack همون چاپ کردن مقادیر داخل stack هستش.

کد بالا یه جواب رو در صورت وجود واسه ما پیدا میکنه و لزوماً کوتاهترین مسیر هم نیست.

اگه میخوای تمام مسیرها رو چاپ کنی باید خروجی تابعت رو void بزاری و تمام if ها غیر از اون شرطی که چک میکنه به w رسیدیم یا نه رو برداری و return ها رو هم برداری.

اگه میخوای مسیر بهینه رو هم به دست بیاری باید از روش چاپ کردن تمام مسیرها که همین بالا گفتم استفاده کنی. یه متغیر MIN باید در نظر بگیری که طول کوتاهترین مسیر هستش. و یه stack کمکی هم لازم داری. هر وقت که به خونه ی w رسیدیم باید length الآن stack رو با MIN مقایسه کنی، اگه MIN از stack.size بیشتر بود باید MIN رو بزاری stack.size و مقادیر stack رو هم توی stack کمکی کپی کنی. وقتی که کلاً از تابع runmaze خارج شدی، مقادیر stack کمکی حاوی کوتاهترین مسیر از منبع به مقصد هستند.