maze.cpp

自定义迷宫

# include<iostream>
using namespace std;
# define MaxSize 100
int mazedata[MaxSize][MaxSize];

typedef struct mazestack        //定义迷宫的栈
{ 
	int left;
	int right;
	int direct;
    struct mazestack *next;
} LinkStack;

void InitStack(LinkStack *&ls)       //初始化栈
{
	ls=(LinkStack *)malloc(sizeof(LinkStack));
	ls->direct=0;
	ls->left=0;
	ls->right=0;
}

void push(LinkStack *&ls,int i,int j,int k)      //进栈
{   
	LinkStack *p;
	p=(LinkStack *)malloc(sizeof(LinkStack));
	p->left=i;
	p->right=j;
	p->direct=k;
	p->next=ls;
	ls=p;
}


int pop(LinkStack *&ls)                 //退栈
{
	LinkStack *p;
	if(ls==NULL)
		return 0;
	else
	{
		p=ls;
		ls=p->next;
		free(p);
		return 1;
	}
}









int save_mazedata(int m,int n)         //读取mazedata.txt中迷宫数据，并存放在数组mazedata[][]中
{
	char c;
    int i,j;
	FILE *fp=fopen("mazedata.txt","r+b");
	if(fp==NULL)
	{
		cout<<"文件打开失败！";
		return -1;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
		    fread(&c,sizeof(char),1,fp);
		    mazedata[i][j]=c-48;
		}
		fseek(fp,sizeof(char)+1,SEEK_CUR);
	}
	fclose(fp);
	for(i=0,j=0;j<=n;j++)   //以下四个for为初始迷宫四周的强
		mazedata[i][j]=3;
    for(i=0,j=0;i<=m;i++)
		mazedata[i][j]=3;
    for(i=m+1,j=0;j<=n+1;j++)
		mazedata[i][j]=3;
	for(i=0,j=n+1;i<=m+1;i++)
		mazedata[i][j]=3;
	return 0;
}



void printmaze(int m,int n)    //将迷宫数组中的数据翻译并打印出来
{
	for(int i=0;i<=m+1;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			if(mazedata[i][j]==3)//mazedata[i][j]==3为墙
				cout<<"~"<<" ";
			if(mazedata[i][j]==1)//(mazedata[i][j]==1)为迷宫中阻碍
				cout<<"*"<<" ";
			if(mazedata[i][j]==-1)//(mazedata[i][j]==-1)为走出迷宫道路
				cout<<">"<<" ";
			if(mazedata[i][j]==0)//(mazedata[i][j]==0)为没走之路
				cout<<"  ";
		}
        cout<<endl;
	}
}





int solvemaze(int m,int n)     //解迷宫算法
{   printmaze(m,n);
	LinkStack *ls;             //sl为迷宫的栈
	InitStack(ls);
	int i=1,j=1,k=0,answernum=1;      //k的作用是为了不让走死胡同弹栈时回头，answernum是记录解迷宫的数目
	int m1,m2,m3,m4,dir=1;            //m1,m2,m3,m4为右，下，左，上（顺时针顺序）四个方向上的数组的值
	do                                //dir用途是判断向哪个走还是退栈
	{   
		if((i==m)&&(j==n))            //到达迷宫终点则输出
		{
			mazedata[i][j]=-1;
			cout<<"解 "<<answernum<<" :"<<endl;
			printmaze(m,n);
			answernum++;
			mazedata[i][j]=0;
		}
		if((i!=ls->left)||(j!=ls->right))   //先将该坐标进栈，direct先令为0，下面判断哪个方向有路后再改正 
		    push(ls,i,j,0);
		if ((dir==5)||((i==m)&&(j==n)))    //如果四面都不能走（即dir==5）或者到达终点则退栈
		{   
			pop(ls);
			mazedata[i][j]=0;              //退栈后将mazedata[i][j]改为0（原先等于－1）
			switch(ls->direct)             //退栈指向的坐标即(i,j)也后退，并且记录k值，避免再走此路线
		{
			case 1:
				j--;k=1;break;
			case 2:
				i--;k=2;break;
			case 3:
				j++;k=3;break;
			case 4:
				i++;k=4;break;
		}
			dir=ls->direct+1;
		}
		m1=mazedata[i][j+1];
	    m2=mazedata[i+1][j];
		m3=mazedata[i][j-1];
		m4=mazedata[i-1][j];
		if(dir==1)                      //dir==1表示向右看，下同
		{
			if((m1==0)&&(k!=1))         //再判断右面是否能走通以及是否是刚退栈的路线
			{
				ls->direct=1;
			    mazedata[i][j]=-1;
			    j++;
				dir=1;
				k=0;
			}
			else dir++;
		}
		if(dir==2)
		{
			if((m2==0)&&(k!=2))
			{
				ls->direct=2;
                mazedata[i][j]=-1;
			    i++;
				dir=1;
				k=0;
			}
			else dir++;
		}
		if(dir==3)
		{
			if((m3==0)&&(k!=3))
			{
				ls->direct=3;
			    mazedata[i][j]=-1;
			    j--;
				dir=1;
				k=0;
			}
		    else dir++;
		}
		if(dir==4)
		{
			if((m4==0)&&(k!=4))
			{
				ls->direct=4;
			    mazedata[i][j]=-1;
			    i--;
				dir=1;
				k=0;
			}
		    else dir++;
		}
		if((ls->left==0)&&(ls->right==0))     //如果退栈退到初始状态，表示所有解法都已找出，则循环结束
		{
			cout<<"That's all!"<<endl;
			return 1;
		}
	}while((ls->left!=0)||(ls->right!=0)||(dir<=4));//如果栈的状态变为初始状态且四个方向都走不同则退出
	return 0;
}








int main()
{
	int m,n;
	cout<<"迷宫行数：";
	cin>>m;
	cout<<"迷宫列数：";
	cin>>n;
    save_mazedata(m,n);     //读取迷宫数据
	solvemaze(m,n);         //解迷宫
	return 0;
}