第2个回答 2009-11-24
#include<stdio.h>
#define MAX_STACK_SIZE 100
#define MAX_SIZE 10
typedef struct{
short int vert;
short int horiz;
}offsets;
offsets move[8];
typedef struct{
short int row;
short int col;
short int dir;
}element;
element stack[MAX_STACK_SIZE];
int maze[MAX_SIZE][MAX_SIZE],mark[MAX_SIZE][MAX_SIZE];
int TRUE=1,FALSE=0,EXIT_ROW,EXIT_COL,top;
void push(int *top,element item);
element pop(int *top);
void main()
{
move[0].vert=-1; move[0].horiz=0;
move[1].vert=-1; move[1].horiz=1;
move[2].vert=0; move[2].horiz=1;
move[3].vert=1; move[3].horiz=1;
move[4].vert=1; move[4].horiz=0;
move[5].vert=1; move[5].horiz=-1;
move[6].vert=0; move[6].horiz=-1;
move[7].vert=-1; move[7].horiz=-1;
int i,j,row,col,next_row,next_col,dir,found=FALSE;
element position;
printf("输入迷宫的行数与列数:\n");
scanf("%d%d",&row,&col);
for(i=0;i<=row+1;i++)
maze[i][0]=1;
for(i=0;i<=col+1;i++)
maze[0][i]=1;
for(i=row+1;i>=0;i--)
maze[i][col+1]=1;
for(i=col+1;i>=0;i--)
maze[row+1][i]=1;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
scanf("%d",&maze[i][j]);
EXIT_ROW=row;
EXIT_COL=col;
mark[1][1]=1;
top=0;
stack[0].row=1;
stack[0].col=1;
stack[0].dir=1;
while(top>-1&&!found){
position=pop(&top);
row=position.row;
col=position.col;
dir=position.dir;
while(dir<8&&!found){
next_row=row+move[dir].vert;
next_col=col+move[dir].horiz;
if(next_row==EXIT_ROW&&next_col==EXIT_COL)
found=TRUE;
else if(!maze[next_row][next_col]&&!mark[next_row][next_col]){
mark[next_row][next_col]=1;
position.row=row;
position.col=col;
position.dir=++dir;
push(&top,position);
row=next_row;
col=next_col;
dir=0;
}
else ++dir;
}
}
if(found){
printf("The path is:\n");
printf("row col\n");
for(i=0;i<=top;i++)
printf("%2d%5d\n",stack[i].row,stack[i].col);
printf("%2d%5d\n",row,col);
printf("%2d%5d\n",EXIT_ROW,EXIT_COL);
}
else printf("The maze does not have a path\n");
}
void push(int *top,element item)
{
if(*top>=MAX_STACK_SIZE-1) printf("The stack is full\n");
else stack[++*top]=item;
}
element pop(int *top)
{
if(*top==-1){
printf("The stack is empty\n");
return stack[-1];
}
else return stack[(*top)--];
}
第3个回答 2009-11-24
#include"stdio.h"
#define M 6
#define N 8
#define MAX 100
typedef struct
{ int x;
int y;
}item;
typedef struct
{ int x,y,d;
}sanyuan;
typedef struct
{ sanyuan elem[MAX];
int top;
}sqstack;
void Initstack(sqstack *s)
{s->top=-1;}
int stackempty(sqstack *s)
{if(s->top==-1) return 1;
else return 0;}
void push(sqstack *s,sanyuan e)
{if(s->top==MAX-1)
{printf("stack is full\n");
return;}
s->top++;s->elem[s->top]=e;}
sanyuan pop(sqstack *s,sanyuan e)
{
e=s->elem[s->top];
s->top--;
return e;
}
void printpath(sqstack *s)
{sanyuan temp;
printf("(%d,%d)<==",M,N);
while(!stackempty(s))
{temp=pop(s,temp);
printf("(%d,%d)<==",temp.x,temp.y);
}
printf("\n");
}
int mazepath()
{
int maze[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1},{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},{1,0,1,1,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,1,1}};
item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
sqstack *s;sanyuan temp;
int x,y,d,i,j;
Initstack(s);
temp.x=1;temp.y=1;temp.d=-1;
push(s,temp);
while(!stackempty(s))
{pop(s,temp);
x=temp.x;y=temp.y;d=temp.d+1;
while(d<8)
{i=x+move[d].x;
j=y+move[d].y;
if(maze[i][j]==0)
{temp.x=x;temp.y=y;temp.d=d;
push(s,temp);
x=i;y=j;
maze[x][y]=-1;
if(x==M&&y==N)
{printpath(s);
return 1;
}
else d=0;
}
else d++;
}
}
return 0;
}
void main()
{
mazepath();
}