#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#define MAXSIZE 50

#define ERROR -1

#define OK 0

#define FALSE 0

#define TRUE 1

typedef 

enum{RIGHT,DOWN,LEFT,UP} Direction;

typedef 

enum{YES,NO} MarkTag;

typedef 

struct position{

    

int x;

    

int y;

}Position;

typedef 

struct{

    

int order;

    Position seat;

    Direction di;

}SElemType;

typedef 

struct{

    SElemType *elem;

    

int top;

}Stack;

char maze[MAXSIZE+

2][MAXSIZE+

2];

int InitStack(Stack *S){

    S->elem=(SElemType *)malloc(MAXSIZE*MAXSIZE*

sizeof(SElemType));

    

if(!S->elem) 

return ERROR;

    S->top=

0;

    

return OK;

}

int Push(Stack *S,SElemType e){

    

if(S->top>=MAXSIZE*MAXSIZE) 

return ERROR;

    S->elem[S->top++]=e;

    

return OK;

}

int Pop(Stack *S,SElemType *e){

    

if(S->top<=

0) 

return ERROR;

    *e=S->elem[--S->top];

    

return OK;

}

int Empty(Stack S){

    

if(S.top==

0) 

return TRUE;

    

return FALSE;

}

int createMaze(

char *filename,Position *startpos,Position *endpos){

    FILE *fp;

    

int i,j,rows,cols,temp;

    Position start,end;

    fp=fopen(filename,

"

r

");

    

if(!fp){

        printf(

"

open file %s error!\n

",filename);

        

return ERROR;

    }

    

if(!feof(fp)){

        fscanf(fp,

"

%d %d 

",&rows,&cols);

        fscanf(fp,

"

%d %d 

",&start.x,&start.y);

        fscanf(fp,

"

%d %d 

",&end.x,&end.y);

    }

    

for(i=

1;i<=rows;i++){

        

for(j=

1;j<=cols;j++){

            fscanf(fp,

"

%d 

",&temp);

            maze[i][j]=

48+temp;

        }

    }

    fclose(fp);

    

    

for(i=

0,j=

0;i<=rows+

1;i++)maze[i][j]=

'

1

';

    

for(i=

0,j=cols+

1;i<=rows+

1;i++)maze[i][j]=

'

1

';

    

for(i=

0,j=

0;j<=cols+

1;j++)maze[i][j]=

'

1

';

    

for(i=rows+

1,j=

0;j<=cols+

1;j++)maze[i][j]=

'

1

';

    *startpos=start;

    *endpos=end;

    

    

for (i=

0;i<=rows+

1;i++)

    {

        

for(j=

0;j<=cols+

1;j++)

        {

            printf(

"

%c

",maze[i][j]);

        }

        printf(

"

\n

");

    }

    

return OK;

}

int canPass(Position curpos){

    

if(maze[curpos.x][curpos.y]==

'

0

') 

return TRUE;

    

return FALSE;

}

void markPos(Position curpos,MarkTag tag){

    

switch(tag){

        

case YES:maze[curpos.x][curpos.y]=

'

.

';

break;

        

case NO:maze[curpos.x][curpos.y]=

'

#

';

break;

    }

}

Position nextPos(Position curpos,Direction dir){

    Position nextpos;

    

switch(dir){

        

case RIGHT:nextpos.x=curpos.x;nextpos.y=curpos.y+

1;

break;

        

case DOWN:nextpos.x=curpos.x+

1;nextpos.y=curpos.y;

break;

        

case LEFT:nextpos.x=curpos.x;nextpos.y=curpos.y-

1;

break;

        

case UP:nextpos.x=curpos.x-

1;nextpos.y=curpos.y;

break;

    }

    

return nextpos;

}

Direction nextDir(Direction dir){

    

switch(dir){

        

case RIGHT:

return DOWN;

        

case DOWN:

return LEFT;

        

case LEFT:

return UP;

    }

}

int Solve(Stack *S,Position start,Position end){

    Position curpos;

    SElemType e;

    

int curstep=

1;

    

if(InitStack(S)==ERROR) 

return FALSE;

    curpos=start;

    

do{

        

if(canPass(curpos)){

            markPos(curpos,YES);

            e.order=curstep;e.seat=curpos;e.di=RIGHT;

            Push(S,e);

            

if(curpos.x==end.x && curpos.y==end.y)

                

return TRUE;

            curpos=nextPos(curpos,RIGHT);

            curstep++;

        }

        

else

        {

            

if(!Empty(*S)){

                

if(Pop(S,&e)==ERROR) 

return FALSE;

                

while(e.di==UP && !Empty(*S)){

                    curpos=e.seat;markPos(curpos,NO);

                    

if(Pop(S,&e)==ERROR)

return FALSE;

                }

                

if(e.di!=UP){

                    e.di=nextDir(e.di);

                    Push(S,e);

                    curpos=nextPos(e.seat,e.di);

                }

            }

        }

    }

while(!Empty(*S));

    

return FALSE;

}

void main(

void)

{

    Position startPos,endPos;

    Stack path;

    SElemType e;

    

char *fname=

"

in.txt

";

    

if(createMaze(fname,&startPos,&endPos)==ERROR) 

return;

    Solve(&path,startPos,endPos);

    

while(!Empty(path)){

        Pop(&path,&e);

        printf(

"

(%d,%d)\n

",e.seat.x,e.seat.y);

    }

    system(

"

pause

");

}

 

in.txt

8 8  

1 1 8 8 

0 0 1 0 0 0 1 0 

0 0 1 0 0 0 1 0 

0 0 0 0 1 1 0 0 

0 1 1 1 0 0 0 0 

0 0 0 1 0 0 0 0 

0 1 0 0 0 1 0 0 

0 1 1 1 0 1 1 0 

1 0 0 0 0 0 0 0