主题:算法3.3 P51页结合P46,47页算法(迷宫)
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
struct complex{
int i;
int j;
}
struct SqStack{
complex *base;
complex *top;
int stacksize;
};
bool InitStack(SqStack &S){
S.base=(complex*)malloc(STACK_INIT_SIZE*sizeof(complex));
if(!S.base)return false;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return true;
}
bool GetTop(SqStack &S,complex &e)
{
if(S.top==S.base) return false;
e=*(S.top-1);
return true;
}
bool Push(SqStack &S,complex e)
{
if((S.top-S.base)>=S.stacksize)
{
S.base=(complex*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(complex));
if(!S.base)return false;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return true;
}
bool Pop(SqStack &S,complex &e,int &a[10][10])
{
if(S.top==S.base)return false;
a[(S.top-1)->i][(S.top-1)->j]=1;
e=*S.top--;
return true;
}
void DestoryStack(SqStack &S)
{
if(S.base!=NULL)
free(S.base);
}
void ClearStack(SqStack &S)
{
S.top=S.base;
}
bool StackEmpty(SqStack S)
{
if(S.base==S.top)
return true;
else
return false;
}
bool MazePath(int &a[10][10],complex start,complex end)
{
int col=1,row=1;
SqStack S,S1;
InitStack(SqStack &S);
InitStack(SqStack &S1);
if(start.i-end.i)
col=-1;
if(start.j-end.j)
row=-1;
complex p=start,e;
bool flag=true;
while(p!=end&&flag)
{
flag=false;
if(!a[p.i+col][p.j])
{
p.i=p.i+col;
Push(S,p);
flag=true;
}
else
if(!a[p.i][p.j+1])
{
p.j=p.j+row;
Push(S,p);
flag=true;
}
else
{
flag=Pop(S,e,a);
}
}
while(!StackEmpty(SqStack S))
{
GetTop(S,e);
Push(S1,e);
Pop(S,e,a);
}
while(!StackEmpty(SqStack S1))
{
GetTop(S1,e);
printf("\n %d %d",e.i,e.j);
Pop(S1,e,a);
}
DestoryStack(S1);
DestoryStack(S);
}
//////////////
void main()
{
int a[10][10],i,j;
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{
a[i][j]=0;
}
}
for(i=0; i<10; i++)
{
a[1][i]=1;
a[9][i]=1;
}
for(i=1; i<10; i++)
{
a[i][0]=1;
a[i][9]=1;
}
a[1][3]=a[2][3]=a[1][7]=a[2][7]=a[3][5]=a[3][6]=a[4][2]=a[4][3]=a[4][4]=a[5][4]=a[6][2]=a[6][6]=a[7][2]=a[7][3]=a[7][4]=a[7][6]=a[7][7]=a[8][1]=1;
complex start,end;
bool flag=false;
do
{
printf("输入开始位置:(%d %d)");
scanf("%d %d",&start.i,&start.j);
if(a[start.i][start.j])
{
printf("开始位置不能为1(那是墙)\n");
}
else
flag=true;
}while(!flag);
flag=false;
do
{
printf("输入开始位置:(%d %d)");
scanf("%d %d",&end.i,&end.j);
if(a[end.i][end.j])
{
printf("开始位置不能为1(那是墙)\n");
}
else
flag=true;
}while(!flag);
MazePath(a,start,end);
}
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
struct complex{
int i;
int j;
}
struct SqStack{
complex *base;
complex *top;
int stacksize;
};
bool InitStack(SqStack &S){
S.base=(complex*)malloc(STACK_INIT_SIZE*sizeof(complex));
if(!S.base)return false;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return true;
}
bool GetTop(SqStack &S,complex &e)
{
if(S.top==S.base) return false;
e=*(S.top-1);
return true;
}
bool Push(SqStack &S,complex e)
{
if((S.top-S.base)>=S.stacksize)
{
S.base=(complex*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(complex));
if(!S.base)return false;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return true;
}
bool Pop(SqStack &S,complex &e,int &a[10][10])
{
if(S.top==S.base)return false;
a[(S.top-1)->i][(S.top-1)->j]=1;
e=*S.top--;
return true;
}
void DestoryStack(SqStack &S)
{
if(S.base!=NULL)
free(S.base);
}
void ClearStack(SqStack &S)
{
S.top=S.base;
}
bool StackEmpty(SqStack S)
{
if(S.base==S.top)
return true;
else
return false;
}
bool MazePath(int &a[10][10],complex start,complex end)
{
int col=1,row=1;
SqStack S,S1;
InitStack(SqStack &S);
InitStack(SqStack &S1);
if(start.i-end.i)
col=-1;
if(start.j-end.j)
row=-1;
complex p=start,e;
bool flag=true;
while(p!=end&&flag)
{
flag=false;
if(!a[p.i+col][p.j])
{
p.i=p.i+col;
Push(S,p);
flag=true;
}
else
if(!a[p.i][p.j+1])
{
p.j=p.j+row;
Push(S,p);
flag=true;
}
else
{
flag=Pop(S,e,a);
}
}
while(!StackEmpty(SqStack S))
{
GetTop(S,e);
Push(S1,e);
Pop(S,e,a);
}
while(!StackEmpty(SqStack S1))
{
GetTop(S1,e);
printf("\n %d %d",e.i,e.j);
Pop(S1,e,a);
}
DestoryStack(S1);
DestoryStack(S);
}
//////////////
void main()
{
int a[10][10],i,j;
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{
a[i][j]=0;
}
}
for(i=0; i<10; i++)
{
a[1][i]=1;
a[9][i]=1;
}
for(i=1; i<10; i++)
{
a[i][0]=1;
a[i][9]=1;
}
a[1][3]=a[2][3]=a[1][7]=a[2][7]=a[3][5]=a[3][6]=a[4][2]=a[4][3]=a[4][4]=a[5][4]=a[6][2]=a[6][6]=a[7][2]=a[7][3]=a[7][4]=a[7][6]=a[7][7]=a[8][1]=1;
complex start,end;
bool flag=false;
do
{
printf("输入开始位置:(%d %d)");
scanf("%d %d",&start.i,&start.j);
if(a[start.i][start.j])
{
printf("开始位置不能为1(那是墙)\n");
}
else
flag=true;
}while(!flag);
flag=false;
do
{
printf("输入开始位置:(%d %d)");
scanf("%d %d",&end.i,&end.j);
if(a[end.i][end.j])
{
printf("开始位置不能为1(那是墙)\n");
}
else
flag=true;
}while(!flag);
MazePath(a,start,end);
}