#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#include "conio.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 100
#define INCREMENT 10
typedef int Status;
typedef struct{
int r;
int c;
}PostType;
typedef struct{
int ord;
PostType seat;
int di;
}SElemType;
typedef struct{
SElemType* base;
SElemType* top;
int stackSize;
}Stack;
Status InitStack(&S){
S.base=(SElemType*)malloc(INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}
Status StackEmpty(Stack S){
if(S.top==S.base)
return TRUE;
return FALSE;
}
Status Push(Stack &S,SElemType e){
if(S.top-S.base >=S.stackSize)
{
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status DestroyStack(Stack &S){
free(S.base);
S.top=S.base;
return OK;
}
#define MAXLEN 10
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];
}MazeType;
Status InitMaze(MazeType &maze){
int m,n,i,j;
printf("Enter row and column numbers: ");
scanf("%d%d",&maze.r,&maze.c);
for(i=0;i<=maze.c+1;i++){
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}
for(i=0;i<=maze.r+1;i++){
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);
while(m!=-1){
if(m>maze.r || n>maze.c)
exit(ERROR);
maze.adr[m][n]='#';
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);
}
return OK;
}
Status Pass(MazeType maze,PostType curpos){
if(maze.adr[curpos.r][curpos.c]==' ')
return TRUE;
else
return FALSE;
}
Status FootPrint(MazeType &maze,PostType curpos){
maze.adr[curpos.r][curpos.c]='*';
return OK;
}
PostType NextPos(PostType &curpos,int i){
PostType cpos;
cpos=curpos;
switch(i){
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
return cpos;
}
Status MarkPrint(MazeType &maze,PostType curpos){
maze.adr[curpos.r][curpos.c]='@';
return OK;
}
Status MazePath(MazeType &maze,PostType start,PostType end){
Stack S;
PostType curpos;
int curstep;
SElemType e;
InitStack(S);
curpos=start;
curstep=1;
do{
if(Pass(maze,curpos)){
FootPrint(maze,curpos);
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e);
if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))
exit(OVERFLOW);
else
return TRUE;
else{
curpos=NextPos(curpos,1);
curstep++;
}
}
else{
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4&&!StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di < 4){
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}
}
}
}while(!StackEmpty(S));
if(!DestroyStack(S))
exit(OVERFLOW);
else
return FALSE;
}
void PrintMaze(MazeType &maze){
int i,j;
printf("\nShow maze path(*---pathway):\n\n");
printf(" ");
for(i=0;i<=maze.r+1;i++)
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++){
printf("%2d",i);
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);
printf("\n\n");
}
}
void main(){
MazeType maze;
PostType start,end;
char cmd;
do{
printf("-------FOUND A MAZEPATH--------\n");
if(!InitMaze(maze)){
printf("\nInitialization errors!!!\n");
exit(OVERFLOW);
}
do{
printf("\nEnter entrance coordinate of the maze: ");
scanf("%d%d",&start.r,&start.c);
if(start.r>maze.r || start.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(start.r>maze.r || start.c>maze.c);
do{
printf("\nEnter exit coordinate of the maze: ");
scanf("%d%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf("\nNo path from entrance to exit!\n");
else
PrintMaze(maze);
printf("\nContinue?(y/n): ");
scanf("%s",&cmd);
}while(cmd=='y' || cmd=='Y');
}
刚学C，无能为力啊。