main.cpp

人工智能中的经典的迷宫算法

//Maze
/*
   This is a maze question.
   MAZE[ROW][COLUMN] 表示迷宫
   0:表示路通，能走
   1:障碍，不能走
   2:右方过来
   3:上方过来
   4:左方过来
   5:下方过来

  success:函数标记符号
  1:有通路
  -1:没有通路

*/

#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#define ROW 1000
#define COLUMN 1000

int MAZE[ROW][COLUMN]={0};
int SUCCESS=2;
int MR=0,MC=0;

void main()
{
	void setMaze();                              // 设置迷宫的函数
	void printMaze();                            //打印迷宫的函数
	void walkMaze();                      // 走迷宫的函数	                            
	void printMazeRoad();                         // 打印迷宫通路的函数

	cout<<endl<<"This is a maze program";
	
	//设置迷宫的障碍
	setMaze();

	if(((MR<=0)||(MR<=0))||((MR>=ROW)||(MC>=COLUMN)))
	{
		cout<<endl<<"非法输入，迷宫构造失败！"<<endl;
		getch();
		return;
	}

	//打印迷宫
	printMaze();

	//走迷宫
	cout<<endl<<"begin walk the maze.......";

	walkMaze();

	//打印迷宫通路

	printMazeRoad();
	cout<<endl<<"The Maze program is finished!"<<endl;
	getch();

	
}

// 设置迷宫的函数
void setMaze()
{
	cout<<endl<<"迷宫以二维数组muse[m][n]表示,第一个元素为入口,最后一个元素为出口.";
	cout<<endl<<"下面进行迷宫的设定...";
	char m,n;
	cout<<endl<<"默认迷宫为5*5矩阵,是否自己设定迷宫的大小 y/n?";
	cin>>m;
	if((m=='y')||(m=='Y'))
	{
		cout<<endl<<"请输入迷宫的行数m,m>0,m<1000(太大没必要):";
		cin>>MR;
		cout<<endl<<"情书入迷宫的列数n,n>0,m<1000(太大没必要):";
		cin>>MC;
		if(((MR<=0)||(MR<=0))||((MR>=ROW)||(MC>=COLUMN)))
			return;
	}
	else
	{
		MR=5;
		MC=5;
	}
    cout<<endl<<"默认迷宫有一条路径,是否自己设定迷宫的障碍 y/n:?";
	cin>>n;
	if((n=='y')||(n=='Y'))
	{
		cout<<endl<<"输入m,n 表示迷宫muse[m][n]处是障碍,设置完成请输入-1!"<<endl;
		int ro,co;
		do
		{
			cout<<endl;
			cout<<"m=";
			cin>>ro;
			if(ro==-1)
				break;
			cout<<"n=";
			cin>>co;
			if(co==-1)
				break;
			if((ro>=0)&&(ro<MR)&&(co>=0)&&(co<MC))
			  MAZE[ro][co]=1;

		}while(1);


	}
	else
	{
		for(int i=0;i<MR;i++)
			for(int j=0;j<MC;j++)
				MAZE[i][j]=1;

		MAZE[0][0]=MAZE[MR-1][MC-1]=0;
		int x=0,y=0;
		while((x!=MR-1)||(y!=MC-1))
		{
			MAZE[x][y]=0;
			if(x+1<MR)
				x=x+1;
			else if(y+1<MC)
				y=y+1;
		}
		
	}


}

//打印迷宫的函数
void printMaze()
{
	if((MC>25)||(MR>100))
	{
		cout<<endl<<"迷宫大，不方便打印！";
		return;
	}
	cout<<endl<<"This is the maze:"<<endl;
		for (int i=0;i<MR;i++)
		for(int j=0;j<MC;j++)
		{
			cout<<MAZE[i][j]<<"  ";
			if(j==MC-1)
				cout<<endl;
		}
	
}


// 走迷宫的函数
void walkMaze()
{

	if((MAZE[0][0]==1)||(MAZE[MR-1][MC-1]==1))     //入口与出口不通          
	{
		SUCCESS=0;
		return;

	}

	int m=0,n=0;
 	while(SUCCESS==2)
	{
         if((m==MR-1)&&(n==MC-1))             //找到出口
		 {
			 SUCCESS=1;
			 return;

		 }
		 else
		 {
			 if((m==0)&&(n==0))
			 {
				 if((n+1<MC)&&(MAZE[m][n+1]==0))
				 {
					 n=n+1;
					 MAZE[m][n]=2;
				 }
				 else if((m+1<MR)&&(MAZE[m+1][n]==0))
				 {

					 m=m+1;
					 MAZE[m][n]=3;

				 }
				 else
				 {
					 SUCCESS = 0;
					 return;
				 }

			 }

			 else
			 {
				 	if(MAZE[m][n]==2)
						{
							if((n+1<MC)&&(MAZE[m][n+1]==0))
							{
								n=n+1;
								MAZE[m][n]=2;
							}
							else if((m+1<MR)&&(MAZE[m+1][n]==0))
							{	
								 m=m+1;
								 MAZE[m][n]=3;
							}
							else if((m>0)&&(MAZE[m-1][n]==0))
							{
							     m=m-1;
								 MAZE[m][n]=5;
							}
							else 
							{
								 MAZE[m][n]=10;								
								 n=n-1;
							}
						}

					else if(MAZE[m][n]==3)
					{
						if((n+1<MC)&&(MAZE[m][n+1]==0))
						{
							n=n+1;
							MAZE[m][n]=2;
						}
					
						else if((m+1<MR)&&(MAZE[m+1][n]==0))
						{
							m=m+1;
							MAZE[m][n]=3;
						}
						else if((n>0)&&(MAZE[m][n-1]==0))
						{
							n=n-1;
							MAZE[m][n]=4;
						}
						else
						{
							MAZE[m][n]=10;
							m=m-1;
						}
					}

					else if(MAZE[m][n]==4)
					{
						if((m+1<MR)&&(MAZE[m+1][n]==0))
						{
							m=m+1;
							MAZE[m][n]=3;
						}
						else if((n>0)&&(MAZE[m][n-1]==0))
						{
							n=n-1;
							MAZE[m][n]=4;
						}
						else if((m>0)&&(MAZE[m-1][n]==0))
						{
							m=m-1;
							MAZE[m][n]=5;
						}
						else
						{
							MAZE[m][n]=10;
							n=n+1;
						}
					}

				
					else
					{
						if((n+1<MC)&&(MAZE[m][n+1]==0))
						{
							n=n+1;
							MAZE[m][n]=2;
						}					
						else if((n>0)&&(MAZE[m][n-1]==0))
						{
							n=n-1;
							MAZE[m][n]=4;
						}
						else if((m>0)&&(MAZE[m-1][n]==0))
						{
							m=m-1;
							MAZE[m][n]=5;
						}
					    else
						{
							MAZE[m][n]=10;
							m=m+1;						
						}
					}

			 }

			 		 
		 }

   }
}



// 打印迷宫通路的函数
void printMazeRoad()
{
	if(SUCCESS==1)
	{
		int i=1;
		cout<<endl<<"迷宫路径如下："<<endl;
		int m=MR-1,n=MC-1;
		int mb=m,nb=n;
		while(MAZE[MR-1][MC-1]!=0)
		{
			m=MR-1,n=MC-1;
			mb=m,nb=n;
			while(MAZE[m][n]!=0)
			{
				if(MAZE[m][n]==2)
				{
					mb=m;
					nb=n;
					n=n-1;
				}
				else if(MAZE[m][n]==3)
				{
					mb=m;
					nb=n;
                    m=m-1;
				}
				else if(MAZE[m][n]==4)
				{
					mb=m;
					nb=n;
					n=n+1;

				}
				else
				{

					mb=m;
					nb=n;
					m=m+1;
				}


			}

			cout<<"<"<<m<<","<<n<<">  ";
			MAZE[mb][nb]=0;
			if(i%7==0)
				cout<<endl;
			i++;
	
		}
		cout<<"<"<<MR-1<<","<<MC-1<<">  ";




	}
	else
		cout<<endl<<"迷宫不存在从入口到出口的路径！";

}