#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define MAXSIZE 50
using namespace std;
typedef struct{
int x,y;
}pot;
int choices[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向数组
int flag=0;
void msgbox()
{
printf("-------------------------------------------\n");
printf("-------------迷宫非递归编程游戏------------\n");
printf("- -\n");
printf("- 制作者：徐奕 学号：E21614061 -\n");
printf("- -\n");
if(flag==0)
{
printf("-------------------------------------------\n");
system("pause");
flag=1;
}
else
{
printf("- 注意：迷宫最外层不计数 -\n");
printf("- -\n");
printf("- 基本操作： -\n");
printf("- 开始游戏-->S 退出游戏-->E -\n");
printf("- -\n");
printf("-------------------------------------------\n");
}
}
void cur_sys()
{
system("pause");
system("cls");
}
class point{
private:
int x,y;
int d;
public:
pot start,ending;
void MazePath(pot start,pot ending,int maze[MAXSIZE][MAXSIZE],int m,int n);
//迷宫解的路径
void initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n);
//初始化迷宫路径，随机生成
void rewrite(int maze[MAXSIZE][MAXSIZE],int m,int n);
//随机生成的迷宫可能没有通路，利用此函数修改迷宫
};
typedef struct LStackNode
{
point elem;
struct LStackNode *next;
}LStack,*Stack;
Stack InitStack(Stack S)
{
S=NULL;
return S;
}
int StackEmpty(Stack S)
{
if(S==NULL) return 1;
else return 0;
}
Stack Push(Stack S,point e)
{
Stack P;
P=(Stack)malloc(sizeof(LStack));
P->elem=e;
P->next=S;
S=P;
return S;
}
Stack DelTop(Stack S) //删除栈头
{
Stack P;
P=S;
if(!StackEmpty(S))
{
S=S->next;
free(P);
return S;
}
}
point Pop(Stack S,point e) //返回栈顶
{
if(!StackEmpty(S))
{
e=S->elem;
return e;
}
}
void point::MazePath(pot start,pot ending,int maze[MAXSIZE][MAXSIZE],int m,int n)
{
int i,j,d;
int a,b;
point elem,e;
Stack S1,S2;
S1=InitStack(S1);
S2=InitStack(S2);
maze[start.x][start.y]=2; //修改入口坐标，做标记
elem.x=start.x;
elem.y=start.y;
elem.d=0; //开始为0
S1=Push(S1,elem);
while(!StackEmpty(S1))
{
elem=Pop(S1,elem);
S1=DelTop(S1);
i=elem.x;
j=elem.y;
d=elem.d+1;
while(d<=4)
{
a=i+choices[d-1][0];
b=j+choices[d-1][1];
if(a==ending.x&&b==ending.y&&maze[a][b]==0) //出口
{
elem.x=i;
elem.y=j;
elem.d=d;
S1=Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=0; //方向输出为0，判断是否为出口
S1=Push(S1,elem);
printf("\n-----------------------------\n\n路径为:(行坐标，列坐标，方向)\n");
while(S1) //逆置序列 并输出路径
{
e=Pop(S1,e);
S1=DelTop(S1);
S2=Push(S2,e);
}
while(S2)
{
e=Pop(S2,e);
S2=DelTop(S2);
if(e.d==1)
printf("-->(%d,%d,右)",e.x,e.y);
else if(e.d==2)
printf("-->(%d,%d,下)",e.x,e.y);
else if(e.d==3)
printf("-->(%d,%d,左)",e.x,e.y);
else if(e.d==4)
printf("-->(%d,%d,上)",e.x,e.y);
else
printf("-->(%d,%d,出口)",e.x,e.y);
maze[e.x][e.y]=3;
}
printf("\n\n");
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++)
if(maze[i][j]==3) printf("0 ");
else printf("1 ");
printf("\n");
}
return;
}//if
if(maze[a][b]==0)
{
maze[a][b]=2;
elem.x=i;
elem.y=j;
elem.d=d;
S1=Push(S1,elem);
i=a; j=b; d=0;
}
d++;
}
}
printf("没有出迷宫的路径\n");
}
void point::initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n)
{
int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
maze[i][j]=rand()%2;
for(i=0;i<=m+1;i++)
{
maze[i][0]=maze[i][n+1]='*';
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=maze[m+1][j]='*';
}
printf("输出迷宫:\n");
for(i=0;i<=m+1;i++)
{
for(j=0;j<=n+1;j++)
{
if((j==0||i==0)||(j==n+1||i==m+1))
printf("%c ",maze[i][j]);
else
printf("%d ",maze[i][j]);
}
printf("\n");
}
}
void point::rewrite(int maze[MAXSIZE][MAXSIZE],int m,int n)
{
char a;int i,j;
printf("是否修改某点为0(Y/N)? ");
while((cin>>a)&&a!='N')
{
printf("输入坐标空格分隔：");
int a,b;
scanf("%d %d",&a,&b);
maze[a][b]=0;
system("cls");msgbox();
printf("此刻迷宫:\n");
for(i=0;i<=m+1;i++)
{
for(j=0;j<=n+1;j++)
{
if((j==0||i==0)||(j==n+1||i==m+1))
printf("%c ",maze[i][j]);
else
printf("%d ",maze[i][j]);
}
printf("\n");
}
printf("是否继续修改(Y/N)?\n");
}
}
int main()
{
int maze[MAXSIZE][MAXSIZE];
point Maze;
msgbox();
int m,n; //迷宫行列
system("cls");
msgbox();
char x;
printf("输入操作\n-");
while(cin>>x)
{
switch(x)
{
case 'S':cur_sys();msgbox();
printf("输入迷宫的行数m和列数n(空格键区分)\n");
scanf("%d%d",&m,&n);
Maze.initmaze(maze,m,n);
Maze.rewrite(maze,m,n);
printf("输入入口坐标和出口坐标(格式X1 Y1 X2 Y2回车)\n");
scanf("%d %d %d %d",&Maze.start.x,&Maze.start.y,&Maze.ending.x,&Maze.ending.y);
Maze.MazePath(Maze.start,Maze.ending,maze,m,n);
cur_sys();msgbox();printf("输入操作\n-");
break;
case 'E':exit(0);
default:cur_sys();msgbox();printf("输入操作\n-");continue;
}
}
}
