منبع اصلی نوشتار زیر در این لینک قرار دارد

برنامه حرکت موش در هزار تو – rat in a maze

rat maze cheese برنامه حرکت موش در هزار تو   rat in a maze

برنامه حرکت موش در هزار تو (ماز) یا همون rat in maze  یکی از بهترین سوال های مربوط به ساختمان داده است که می توان از آن برای آموزش پشته (Queue) و استک (Stack) استفاده کرد .

در این برنامه قرار است یک موش در هزار تو قرار بگیرد و راه خود را به یک خانه ی خاص که پنیر در آن قرار دارد پیدا کند .مانند شکل زیر (رنگ سبز نقطه آغاز ،رنگ زرد پنیر ،رنگ سفید هم دیوار است):

rat0 برنامه حرکت موش در هزار تو   rat in a maze

ما در این پست موش را با استفاده از صف (Queue) به پنیر می رسانیم و اینگونه عمل می کنیم :

ابتدا خانه های اطراف خانه ی شروع را با مقدار یک پر می کنیم :

rat1 برنامه حرکت موش در هزار تو   rat in a maze بعد از اینکه این دو خانه را پر کردیم آن ها را در صف پوش  (PUSH) می کنیم ، در مرحله بعد یکی از خانه ها را از صف می خوانیم و خانه های اطراف آن را با مقدار ۲ پر می کنیم و خانه هایی را که پر کرده ایم درون صف پوش می کینم و بعد یک خانه ی دیگر از استک می خوانیم و این کار را دوباره و دوباره انجام می دهیم تا به پنیر برسیم مانند شکل های زیر:

rat2 برنامه حرکت موش در هزار تو   rat in a maze

rat4 برنامه حرکت موش در هزار تو   rat in a maze

rat5 برنامه حرکت موش در هزار تو   rat in a maze rat6 برنامه حرکت موش در هزار تو   rat in a maze

rat8 برنامه حرکت موش در هزار تو   rat in a maze مسییر زرد نشان دهنده راه موش است .در برنامه ای که کدش در پایین آمده در قسمت make map  (ساختن نقشه) فرد یک نقشه ایجاد می کند که نقشه یک آرایه دو در دو از اعداد صحیح است و مقدار -۱ نشان دهنده دیوار ،مقدار -۲ نشان دهنده پنیر یا همان خانه هدف است و عدد -۳ که بعد از فراخوانی تابع solve در آرایه قرار می گیرد مسیر را مشخص می کند

و این هم کد برنامه حرکت موش در هزار تو Rat in maze  با زبان سی پلاس پلاس :

 

// rate in maze(queue).cpp 
//open-mind.ir

#include "stdafx.h"
#include <iostream>
#include <queue>

using namespace std;

//class posistin contain int x for x-Axis and int y for y-Axis.
//class position = cartesian coordinates;
class position
{
public:
	int x;
	int y;
	position()
	{
		x = 0;
		y = 0;
	}
	position(int X,int Y)
	{
		x = X;
		y = Y;
	}
};

//------------------------Show-------------------------
void show(int **A,int row,int col)
{
	char ch = 178;
	for (int i = 0; i < col+1; i++)
	{
		cout<<ch<<ch;
	}
	cout<<ch;
	cout<<endl;
	for (int i = 0; i < row; i++)
	{
		cout<<ch<<" ";
		for (int j = 0; j < col; j++)
		{
			if (A[i][j] == -1)
			{
				cout<<ch<<ch;
				continue;
			}
			if (A[i][j] == -3)
			{
				cout<<"."<<" ";
				continue;
			}
			if (A[i][j] == -2)
			{
				cout<<"*"<<" ";
				continue;
			}
			cout<<"  ";
		}
		cout<<ch<<" ";
		cout<<endl;
	}
	for (int i = 0; i < col+1; i++)
	{
		cout<<ch<<ch;
	}
	cout<<ch;
	cout<<endl;
}
//-----------------------------------------------------

//this function take:
//int **A  : this is map of maze. -1 for wall , -2 for Goalpoint and -3 for way that put in array after solve
//int row  : this is number of row.
//int col  : this is number of col.
//int start: start position.
void solve(int **A,int row,int col,position start)
{
	//char ch;
	queue<position> que;
	position temppos;

	bool ExistWay = false;
	A[start.x][start.y] = 1;
	que.push(start);

	while (que.size() != 0)
	{	
		temppos = que.front();
		//cout<<"*********"<<endl;
		que.pop();

		if (temppos.x > 0)
		{
			if (A[temppos.x-1][temppos.y] == 0 || A[temppos.x-1][temppos.y] == -2)
			{
				if (A[temppos.x-1][temppos.y] == -2)
				{
					ExistWay = true;
					break;
				}
				A[temppos.x-1][temppos.y] = A[temppos.x][temppos.y] + 1;  
				que.push(position(temppos.x-1,temppos.y));
			}
			//show(A,row,col);
			//cin>>ch;
		}
		if (temppos.x < row-1)
		{
			if (A[temppos.x+1][temppos.y] == 0 || A[temppos.x+1][temppos.y] == -2)
			{
				if (A[temppos.x+1][temppos.y] == -2)
				{
					ExistWay = true;
					break;
				}
				A[temppos.x+1][temppos.y] = A[temppos.x][temppos.y] + 1;
				que.push(position(temppos.x+1,temppos.y));
			}
			//show(A,row,col);
			//cin>>ch;
		}
		if (temppos.y > 0)
		{
			if (A[temppos.x][temppos.y-1] == 0 || A[temppos.x][temppos.y-1] == -2)
			{
				if (A[temppos.x][temppos.y-1] == -2)
				{
					ExistWay = true;
					break;
				}
				A[temppos.x][temppos.y-1] = A[temppos.x][temppos.y] + 1;  
				que.push(position(temppos.x,temppos.y-1));
			}
			//show(A,row,col);
			//cin>>ch;
		}
		if (temppos.y < col-1)
		{
			if (A[temppos.x][temppos.y+1] == 0 || A[temppos.x][temppos.y+1] == -2)
			{
				if (A[temppos.x][temppos.y+1] == -2)
				{
					ExistWay = true;
					break;
				}
				A[temppos.x][temppos.y+1] = A[temppos.x][temppos.y] + 1;
				que.push(position(temppos.x,temppos.y+1));
			}
			//show(A,row,col);
			//cin>>ch;
		}
	} 

	if (ExistWay == false)
	{
		cout<<"No way to target!"<<endl;
	}
	else
	{
		int p;
		int q = A[temppos.x][temppos.y];

		for (int i = 0; i < q; i++)
		{
			p = A[temppos.x][temppos.y]-1;
			A[temppos.x][temppos.y] = -3;

			if (temppos.x > 0)
			{
				if (A[temppos.x-1][temppos.y] == p)
				{
					temppos = position(temppos.x-1,temppos.y-1);								
				}
			}
			if (temppos.x < row-1)
			{
				if (A[temppos.x+1][temppos.y] == p)
				{
					temppos = position(temppos.x+1,temppos.y);								
				}
			}
			if (temppos.y > 0)
			{
				if (A[temppos.x][temppos.y-1] == p)
				{
					temppos = position(temppos.x,temppos.y-1);								
				}
			}
			if (temppos.y < col-1)
			{
				if (A[temppos.x][temppos.y+1] == p)
				{
					temppos = position(temppos.x,temppos.y+1);								
				}
			}
		}
	}
	show(A,row,col);
}
//-----------------------------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
	//-----------------Start-Make-Map------------------
	//-------------------------------------------------
	int row = 10;
	int col = 10;        
	int **A;               //Map
	position start(0,0);   //coordination of start point
	A = new int *[row];

	for (int i = 0; i < col; i++)
	{
		A[i] = new int [col];
	}

	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			A[i][j] = 0;
		}
	}
	A[1][1] = A[1][2] = A[1][3] = A[1][4] = A[0][4] = A[2][1] = A[4][1] = A[5][1] = A[5][0] = -1;//For Wall
	A[3][4] = A[3][5] = A[3][6] = A[3][6] = -1;//For Wall
	A[3][3] = A[4][3] = A[5][3] = A[6][3] = A[8][3] =-1;//For Wall
	A[8][3] = A[9][3] = -1;//For Wall
	A[8][5] = A[7][5] = -1; //For Wall

	A[8][8] = -2;//For Golpoint

	//-----------------End-Make-Map--------------------

	solve(A,row,col,start);

	return 0;
}

 

digg برنامه حرکت موش در هزار تو   rat in a maze   reddit برنامه حرکت موش در هزار تو   rat in a maze   stumbleupon برنامه حرکت موش در هزار تو   rat in a maze   yahoo buzz برنامه حرکت موش در هزار تو   rat in a maze   dzone برنامه حرکت موش در هزار تو   rat in a maze   facebook برنامه حرکت موش در هزار تو   rat in a maze   delicious برنامه حرکت موش در هزار تو   rat in a maze   dotnetkicks برنامه حرکت موش در هزار تو   rat in a maze   dotnetshoutout برنامه حرکت موش در هزار تو   rat in a maze   linkedin برنامه حرکت موش در هزار تو   rat in a maze   technorati برنامه حرکت موش در هزار تو   rat in a maze   twitter برنامه حرکت موش در هزار تو   rat in a maze   google buzz برنامه حرکت موش در هزار تو   rat in a maze   



برچسب ها : , , , ,

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

به اين صفحه امتياز دهيد