#include<stdio.h>
#include<stdlib.h>
#define N 10
#define INIT_STACK_SIZE 20
#define STACKINCREMENT 10
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;

int maze[N][N]={0,0,0,0,0,0,0,0,0,0, //0代表障碍，1代表路径
0,1,1,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0};

SqStack InitStack(SqStack S);
SqStack FoundPath(SqStack S,int maze[N][N]);
SqStack Push(SqStack S,int path);
SqStack Pop(SqStack S,int *path);
int EmptyStack(SqStack S);

int main(void)
{
SqStack S;
int path;

S=InitStack(S);
S=FoundPath(S,maze);
while(!EmptyStack(S))
{
S=Pop(S,&path);
printf("%d->",path);
}
printf("\n");
free(S.base);

return 0;
}

SqStack InitStack(SqStack S)
{
if((S.base=(int *)malloc(INIT_STACK_SIZE * sizeof(int)))==NULL)
{
exit(1);
}
S.top=S.base;
S.stacksize=INIT_STACK_SIZE;

return S;
}

SqStack FoundPath(SqStack S,int maze[N][N])
{
int i,j,path;

i=1; j=1; maze[8][8]=88;
while(maze[i][j]!=maze[8][8])
{
if(maze[i][j]==1)
{
path=10*i+j; //把当前可通路径压入栈
S=Push(S,path);
maze[i][j]=0;
j++; //继续向东走
}
else if(maze[i][j]==0) //当前位置不可通，向南走
{
if(!EmptyStack(S)) //当前栈不空
path=*(S.top-1);
i=path/10;
j=path%10;
i++; //向南走
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向南走不通，向西走
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
j--;
if(maze[i][j]==1) //向西走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向西走不通
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
i--;
if(maze[i][j]==1) //向北走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else //都走不通时
{
if(!EmptyStack(S))
S=Pop(S,&path);
i=path/10;
j=path%10;
}
}//else
}//else
}//else
}//while
if(maze[i][j]==maze[8][8])
{
path=10*i+j;
S=Push(S,path);
}

return S;
}

int EmptyStack(SqStack S)
{
int flag=0;

if(S.top==S.base)
flag=1;

return flag;
}

SqStack Push(SqStack S,int path)
{
*(S.top++)=path;
if(S.top-S.base >= S.stacksize)
{
if((S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(int)))==NULL)
{
exit(1);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}

return S;
}

SqStack Pop(SqStack S,int *path)
{
if(!EmptyStack(S))
*path=*(--S.top);

return S;
}

请诸位指教

俺也写了个迷宫，用递归写的，
其中从文件读的矩阵如下：
1 1 1 1 1 1 1 1
0 0 1 1 0 1 0 1
1 0 0 1 0 0 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 0 1 0 0 1 0 1
1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1
#include <stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
struct matri
{
int num;
int flag;
}matrix[M+2][N+2];
int tag=0; /*标记是否进行下个数字检测*/
int function(int i,int j,int m,int n) /*mn为入口，ij为出口*/
{
matrix[i][j].flag=1;
if(i==m&&n==j)
return 1;
if((matrix[i+1][j].num==1||matrix[i+1][j].flag==1)&&(matrix[i][j+1].num==1||matrix[i][j+1].flag==1)&&(matrix[i+1][j+1].num==1||matrix[i+1][j+1].flag==1)&&(matrix[i-1][j-1].num==1||matrix[i-1][j-1].flag==1)&&(matrix[i-1][j].num==1||matrix[i-1][j].flag==1)&&(matrix[i][j-1].num==1||matrix[i][j-1].flag==1)&&(matrix[i-1][j+1].num==1||matrix[i-1][j+1].flag==1)&&(matrix[i+1][j-1].num==1||matrix[i+1][j-1].flag==1))/*即如果四面八方都被封死，返回０*/
return 0;
/*下面进行八个方向的检验*/
if(matrix[i+1][j].num==0&&matrix[i+1][j].flag==0) /*下*/
{
matrix[i+1][j].flag=1;
if(function(i+1,j,m,n))
{
tag=1;
printf("(%d,%d)->",i+1,j);
}
}
if(matrix[i][j+1].num==0&&matrix[i][j+1].flag==0&&tag==0) /*右*/
{
matrix[i][j+1].flag=1;
if(function(i,j+1,m,n))
{
tag=1;
printf("(%d,%d)->",i,j+1);
}
}
if(matrix[i+1][j+1].num==0&&matrix[i+1][j+1].flag==0&&tag==0) /*右下*/
{
matrix[i+1][j+1].flag=1;
if(function(i+1,j+1,m,n))
{
tag=1;
printf("(%d,%d)->",i+1,j+1);
}
}
if(matrix[i-1][j-1].num==0&&matrix[i-1][j-1].flag==0&&tag==0) /*左上*/
{
matrix[i-1][j-1].flag=1;
if(function(i-1,j-1,m,n))
{
tag=1;
printf("(%d,%d)->",i-1,j-1);
}
}
if(matrix[i-1][j].num==0&&matrix[i-1][j].flag==0&&tag==0) /*上*/
{
matrix[i-1][j].flag=1;
if(function(i-1,j,m,n))
{
tag=1;
printf("(%d,%d)->",i-1,j);
}
}
if(matrix[i][j-1].num==0&&matrix[i][j-1].flag==0&&tag==0) /*左*/
{
matrix[i][j-1].flag=1;
if(function(i,j-1,m,n))
{
tag=1;
printf("(%d,%d)->",i,j-1);
}
}
if(matrix[i-1][j+1].num==0&&matrix[i-1][j+1].flag==0&&tag==0) /*右上*/
{
matrix[i-1][j+1].flag=1;
if(function(i-1,j+1,m,n))
{
tag=1;
printf("(%d,%d)->",i-1,j+1);
}
}
if(matrix[i+1][j-1].num==0&&matrix[i+1][j-1].flag==0&&tag==0) /*左下*/
{
matrix[i+1][j-1].flag=1;
if(function(i+1,j-1,m,n))
{
tag=1;
printf("(%d,%d)->",i+1,j-1);
}
}
}
main()
{

int i,j;
FILE *fp=NULL;
fp=fopen("matrix.txt","r");
if(fp==NULL)
{
printf("Can't open the file.Press any key to exit.");
getch();
exit(0);
}
else
{
for (i=1;i<M+1;i++)
for(j=1;j<N+1;j++)
{
fscanf(fp,"%1d",&matrix[i][j].num);
}
fclose(fp);
}
for(i=0;i<M+2;i++)
{
matrix[0][i].num=1;
matrix[i][0].num=1;
matrix[M+1][i].num=1;
matrix[i][M+1].num=1;
}

for (i=0;i<M+2;i++)
for(j=0;j<M+2;j++)
matrix[i][j].flag=0;
function(7,8,2,1);　/*由（２，１）进，（７，８）出*/
printf("(%d,%d)",7,8);
getch();
}
上面的程序还有点问题，输出的结果不是最优的，也请大家帮忙看看．

[此贴子已经被作者于2006-4-17 17:26:37编辑过]