1.cpp

可以输入一个任意大小的迷宫数据

#include<stdio.h> 
#include<stdlib.h> 

#define OVERFLOW -1 
#define MAX 100

typedef struct 
{ 
   int x,y,d; 
}Data; 

typedef struct 
{ 
   int pos; 
   Data data[MAX]; 
}SNode,*Stack; 

Stack InitStack() 
{ 
   Stack pStack; 
   pStack=(Stack)malloc(sizeof(SNode)); 
   if(!pStack) 
   exit(OVERFLOW); 
   pStack->pos=-1; 
   return pStack; 
} 

int IsEmpty(Stack pstack) 
{ 
   return pstack->pos==-1; 
} 

void Push(Stack pStack,Data x) 
{ 
  if(pStack->pos>=MAX-1) 
  exit(OVERFLOW); 
   else 
   { 
   pStack->pos++; 
    pStack->data[pStack->pos]=x; 
   } 
} 

void Pop(Stack pStack) 
{ 
   if(pStack->pos==-1) 
   exit(OVERFLOW); 
   else 
   pStack->pos--; 
} 

Data GetTop(Stack pStack) 
{ 
   return pStack->data[pStack->pos]; 
} 

Data SetStackElem(int x,int y,int d) 
{ 
   Data element; 
   element.x=x; 
   element.y=y; 
   element.d=0; 
   return element; 
} 

void DisplayPath(Stack pStack) 
{ 
    Data element; 
    printf("The path is:\n"); 
    while(!IsEmpty(pStack)) 
	{ 
      element=GetTop(pStack); 
      Pop(pStack); 
      printf("The node is:(%d,%d)\n",element.x,element.y); 
	} 
} 

void MazePath(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2) 
{ 
   int i,j,k,g,h; 
   Stack pStack; 
   Data element; 
   pStack=InitStack(); 
   maze[x1][y1]=2; 
   Push(pStack,SetStackElem(x1,y1,0)); 

    while(!IsEmpty(pStack))
	{ 
     element=GetTop(pStack); 
     Pop(pStack); 
     i=element.x; 
     j=element.y; 
     k = element.d; 

       while (k<=3)
	   { 
         g=i+direction[k][0]; 
         h=j+direction[k][1]; 
           if(g==x2 && h==y2 && maze[g][h]==0) 
		   { 
            Push(pStack,SetStackElem(i,j,k));
			Push(pStack,SetStackElem(x2,y2,k));
            DisplayPath(pStack); 
            return;
		   } 

           if(maze[g][h]==0) 
		   { 
            maze[g][h]=2; 
            Push(pStack,SetStackElem(i,j,k+1)); 
            i=g; 
            j=h; 
            k=0; 
		   } 
            else 
            k++; 
	   } 
} 
printf("The path has not been found\n"); 
} 

void main() 
{ 
  int direction[4][2]={0,1,1,0,0,-1,-1,0}; 
  int maze[8][11]= 
{ 
  1,1,1,1,1,1,1,1,1,1,1, 
  1,0,1,0,0,1,1,1,0,0,1, 
  1,0,0,0,0,0,1,0,0,1,1, 
  1,0,1,1,1,0,0,0,1,1,1, 
  1,0,0,0,1,0,1,1,0,1,1, 
  1,1,0,0,1,0,1,1,0,0,1, 
  1,1,1,0,1,0,0,0,0,0,1, 
  1,1,1,1,1,1,1,1,1,1,1 
};
   int i,j; 
     printf("The maze is:\n");
    for(i=0;i<8;i++)
	{   for(j=0;j<11;j++)
	    printf("%2d",maze[i][j]);
        printf("\n");
	};
MazePath(maze,direction,1,1,6,9); 
}