迷宫问题c++代码

#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <conio.h>
using namespace std;
#define LEN 12

typedef struct
{
int x,y;
}postype;

typedef struct
{
int m,n;
int arr[LEN][LEN];
}mazetype;

typedef struct
{
int ord;
postype seat;
int di;
}selemtype;
#include "sqstack.cpp"
void initmaze(mazetype &maze,int a[][LEN],int row,int col);
bool mazepath(mazetype &maze,postype start,postype end);
void print_mz(mazetype maze,int row,int col);
status pass(mazetype &maze,postype pos);
void footprint(mazetype &maze,postype pos,int curstep);
void markprint(mazetype &maze,postype pos);
int same(postype curpos,postype end);
postype nextpos(postype pos,int dir);
void readcommand(char &cmd);
void initialization();
void interpret(char cmd);

void main()
{

char cmd;
do
{
initialization();
readcommand(cmd);
interpret(cmd);
}while(cmd!=&apos;q&apos;&&cmd!=&apos;Q&apos;);
}

void initialization()
{
cout<<"求解迷宫---c,退出程序---q"<<endl;
}
void readcommand(char &cmd)
{
do
{
cmd=getche();
}while(cmd!=&apos;c&apos;&&cmd!=&apos;C&apos;&&cmd!=&apos;q&apos;&&cmd!=&apos;Q&apos;);
}

void interpret(char cmd)
{
int rnum,cnum;//rnum表示行数，cnum表示列数
int a2[LEN][LEN];
int i,j;
mazetype ma;
postype from,term;
switch(cmd)
{
case &apos;c&apos;:
case &apos;C&apos;:

FILE *in,*out;
in=fopen("in.data","rb");
out=fopen("out.data","wb");
fscanf(in,"%d",&rnum);
fscanf(in,"%d",&cnum);
for (i=1;i<=rnum;i++)
for(j=1;j<=cnum;j++)
fscanf(in,"%d",&a2[i][j]);

initmaze(ma,a2,rnum,cnum);

cout<<"文件中读取的迷宫数据:"<<endl;

for (i=1;i<=rnum;i++)
{
for(j=1;j<=cnum;j++)
cout<<a2[i][j]<<setw(2);
cout<<endl;
}
cout<<"建立迷宫:"<<endl;
print_mz(ma,rnum,cnum);
/*break;
case &apos;m&apos;:
case &apos;M&apos;:*/
cout<<"请输入迷宫入口和出口坐标位置:"<<endl;
cin>>from.x>>from.y>>term.x>>term.y;

if (mazepath(ma,from,term))
{
cout<<"求得迷宫路径如下:"<<endl;
print_mz(ma,rnum,cnum);
}
else
cout<<"该迷宫没有从给定的入口到出口的路径的信息!"<<endl;
break;
fclose(in);
fclose(out);
/*case &apos;p&apos;:
case &apos;P&apos;:
print_mz(ma,rnum,cnum);*/
}
}

void initmaze(mazetype &maze,int a[][LEN],int row,int col)
{
int i,j;
for(i=1;i<=row+1;i++)
for(j=1;j<=col+1;j++)
maze.arr[i][j]=a[i][j];
for(j=0;j<=col+1;j++)
{
maze.arr[0][j]=1;
maze.arr[row+1][j]=1;
}
for(i=0;i<=row+1;i++)
{
maze.arr[i][0]=1;
maze.arr[i][col+1]=1;
}
}

bool mazepath(mazetype &maze,postype start,postype end)
{
sqstack s;
selemtype e;
postype curpos;
int curstep;
bool found;
initstack(s);
curpos=start;
curstep=1;found=FALSE;
do
{
if(pass(maze,curpos))
{
footprint(maze,curpos,curstep);
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=1;

push(s,e);
if(same(curpos,end)) found=TRUE;
else
{
curpos=nextpos(curpos,1);
curstep++;
}//else
}//if
else
if(!stackempty(s))
{
pop(s,e);
while(e.di==4&&!stackempty(s))
{
markprint(maze,e.seat);
pop(s,e);
curstep--;
}//while
if(e.di<4)
{
e.di++;
push(s,e);
curpos=nextpos(e.seat,e.di);
}//if
}//if
}while(!stackempty(s)&&!found);
return found;
}//mazepath

void print_mz(mazetype maze,int row,int col)
{
int i,j;
for(i=0;i<=row+1;i++)
{
for(j=0;j<=col+1;j++)
cout<<maze.arr[i][j]<<setw(2);
cout<<endl;
}
}

status pass(mazetype &maze,postype pos)
{
return (maze.arr[pos.x][pos.y]==0);
}

void footprint(mazetype &maze,postype pos,int curstep)
{
maze.arr[pos.x][pos.y]=curstep;
}

void markprint(mazetype &maze,postype pos)
{
maze.arr[pos.x][pos.y]=-1;
}

postype nextpos(postype pos,int dir)
{
postype direct[5]={{0,0},{0,1},{1,0},{0,-1},{-1,0}};
pos.x +=direct[dir].x;
pos.y +=direct[dir].y;
return pos;
}

int same(postype curpos,postype end)
{
if (curpos.x==end.x&&curpos.y==end.y) return OK;
else return 0;
}

sqstack.cpp代码:

#include "predef.h"

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int status;
typedef struct
{
selemtype *base;
selemtype *top;
int stacksize;
}sqstack;

status initstack(sqstack &s);
//status destroystack(sqstack&s);
//status clearstack(sqstack &);
status stackempty(sqstack s);
status push(sqstack &s,selemtype e);
status pop(sqstack &s,selemtype &e);

status initstack(sqstack &s)
{
s.base=(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype));
if(!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}

status stackempty(sqstack s)
{
return (s.top==s.base);
}

status push(sqstack &s,selemtype e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(selemtype *)realloc(s.base,(s.stacksize +STACKINCREMENT)*sizeof(selemtype));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return OK;
}

status pop(sqstack &s,selemtype &e)
{
if(s.top==s.base) return ERROR;
e=*--s.top;
return OK;
}

测试数据格式in.data:

3 4
0 0 0 1
1 0 0 1
0 1 0 0