#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK 1024
#define MAX 11
typedef struct _PosType{
int x,y;
}PosType;
typedef struct _SElemType{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct _MazeType{
int matrix[MAX][MAX];
int m,n;
}MazeType;
typedef struct _SqStack{
SElemType *base;
SElemType *top;
int stackSize;
}SqStack;
int InitStack(SqStack *S)
{
S->base = (SElemType *)malloc(MAX_STACK*sizeof(SElemType));
S->top = S->base;
S->stackSize = MAX_STACK;
return 1;
}
int GetTop(SqStack *S, SElemType *e)
{
if(S->top == S->base){
return 0;
}else{
*e = *(S->top - 1);
return 1;
}
}
int Push(SqStack *S, SElemType e)
{
if(S->top - S->base >= S->stackSize){
return 0;
}
*(S->top++) = e;
}
int Pop(SqStack *S, SElemType *e)
{
if(S->top == S->base){
return 0;
}else{
*e = *(--S->top);
return 1;
}
}
int StackEmpty(SqStack *S)
{
if(S->top == S->base){
return 1;
}else{
return 0;
}
}
int ClearStack(SqStack *S)
{
S->top = S->base;
return 1;
}
int PrintStack(SqStack *S)
{
MazeType m;
int i,j;
m.m = 10;
m.n = 10;
for(i=0; i<m.m; i++){
for(j=0; j<m.n; j++){
m.matrix[i][j] = 0;
}
}
SElemType *p = S->base;
while(p != S->top){
printf("(%d,%d) ", p->seat.x, p->seat.y);
m.matrix[p->seat.x][p->seat.y] = 1;
p++;
}
printf("\n");
for(i=0; i<m.m; i++){
for(j=0; j<m.n; j++){
printf(" %d", m.matrix[i][j]);
}
printf("\n");
}
return 1;
}
int MazePath(MazeType maze, PosType start, PosType end)
{
SqStack S;
PosType curpos = start;
InitStack(&S);
SElemType e;
e.ord = 0;
do{
if(maze.matrix[curpos.x][curpos.y] == 1){
maze.matrix[curpos.x][curpos.y]++;//Footprint
e.ord++;
e.seat = curpos;
e.di = 1; //1-4 east, south, west, north
Push(&S, e);
if(curpos.x == end.x && curpos.y == end.y){
printf(" Found path.\n");
PrintStack(&S);
return 1;
}else{
curpos.y++;
}
}else{
/* Update the top element,
* in order to turn to its next direction. */
Pop(&S, &e);
while(e.di==4 && !StackEmpty(&S)){
maze.matrix[e.seat.x][e.seat.y] = 0;
Pop(&S, &e);
}
if(e.di<4){
e.di++;
Push(&S, e);
switch(e.di){
case 1:
e.seat.y++;
break;
case 2:
e.seat.x++;
break;
case 3:
e.seat.y--;
break;
case 4:
e.seat.x--;
break;
}
curpos = e.seat;
}
}
}while(!StackEmpty(&S));
printf(" No path.\n");
return 0;
}
void main()
{
MazeType maze;
PosType start,end;
int i,j,c;
printf("log.anycle.com\n\n");
printf("Original data:\n");
scanf(" %d %d", &maze.m, &maze.n);
for(i=0; i<maze.m; i++){
for(j=0; j<maze.n; j++){
scanf(" %d", &c);
maze.matrix[i][j] = c;
}
}
scanf(" %d %d", &start.x, &start.y);
scanf(" %d %d", &end.x, &end.y);
for(i=0; i<maze.m; i++){
for(j=0; j<maze.n; j++){
printf(" %d", maze.matrix[i][j]);
}
printf("\n");
}
printf("Start:(%d, %d), End:(%d, %d).\n",
start.x, start.y, end.x, end.y );
printf("Maze path:\n");
MazePath(maze, start, end);
}