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

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

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

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

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

مسییر زرد نشان دهنده راه موش است .در برنامه ای که کدش در پایین آمده در قسمت 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;
}