digui.cpp

迷宫问题是一个很古老的问题

#include <iostream.h>
#define Maxsize 100


int maze[14][17]=
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	 1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,
	 1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,
	 1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,
	 1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
	 1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
	 1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,
	 1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,
	 1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
	 1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,
	 1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,
	 1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,
	 1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,
	 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	};
 
int move[9][3]=
	{0,0,0,
	 0,0,1,
	 0,1,1,
	 0,1,0,
	 0,1,-1,
	 0,0,-1,
	 0,-1,-1,
	 0,-1,0,
	 0,-1,1,
	};
 


static int mark[14][17];


bool Maze_path(int i, int j)	//迷宫递归寻路径
{  if(maze[i][j]==1)			//如果要走的这一点不通，直接返回错误
		return false;
	mark[i][j]=1;
	if(i==12&&j==15)			//如果到达出口，返回真
	{
	cout<<"i: "<<i<<"  j:"<<j<<"  next step: "<<1<<endl;
		maze[i][j]=8;
		return true;
	}   
	for(int m=1;m<=8;m++)     //向八个方向进行试探
	{ int g=i+move[m][1];
	  int h=j+move[m][2];
	 if(maze[g][h]==0&&mark[g][h]==0)//如果没有走过，且可以走
		{
		 mark[g][h]=1;
		
		if(Maze_path(g,h))			//如果当前点可以走通，即存在一条路径到达终点
			{
			 cout<<"i: "<<i<<"  j:"<<j<<"  next step: "<<m<<endl;
			 maze[i][j]=8;
			 return true;
			}
		}

	}
if(i==1&&j==1)				//如果返回到（1，1）则返回错误，没有路径能走通
	cout<<"no path!"<<endl;
return false;
}



void main()
{
	Maze_path(1,1);
	for(int i=0;i<14;i++)
	{for(int j=0;j<17;j++)
		cout<<maze[i][j]<<" ";
	 cout<<endl;
	}
}