mazemm.c

用栈实现迷宫算法

#include<stdio.h> 

int mg[10][10]={
    1,1,1,1,1,1,1,1,1,1,
	1,0,0,1,0,0,0,1,0,1,
	1,0,0,1,0,0,0,1,0,1,
	1,0,0,0,0,1,1,0,0,1,
	1,0,1,1,1,1,0,0,0,1,
	1,0,0,0,1,1,1,1,0,1,
	1,1,0,0,0,1,1,1,0,1,
	1,0,0,0,1,1,1,1,0,1,
	1,0,0,0,0,0,0,0,0,1,
	1,1,1,1,1,1,1,1,1,1
};

struct
{ int i;
  int j;
  int di;
}Stack[100];

int top=-1;

int main()
{
    int i,j,di,find,k;
    top++;
    Stack[top].i=1;
    Stack[top].j=1;
    Stack[top].di=-1;
    mg[1][1]=-1;   
    
    while(top>-1)  /*当栈非空时*/
    {  
        i=Stack[top].i;
        j=Stack[top].j;
        di=Stack[top].di;
        if(i==8&&j==8) /*到达出口*/ 
        {
            printf("迷宫路径如下:\n");
            for(k=0;k<=top;k++)
            {
                printf("(%d,%d)\t",Stack[k].i,Stack[k].j);
                if((k+1)%5==0)printf("\n");
            }
            /*printf("\n");*/
            return;
        } 
        find=0;
    while(di<4 && find==0)
    {
    di++;
    switch(di)
    {
        case 0:i=Stack[top].i-1;j=Stack[top].j;
            break;
        case 1:i=Stack[top].i;j=Stack[top].j+1;
            break;
        case 2:i=Stack[top].i+1;j=Stack[top].j;
            break;
        case 3:i=Stack[top].i;j=Stack[top].j-1;
            break;
    }
    if (mg[i][j]==0) 
    find=1;
    } 
if(find==1)
{Stack[top].di=di;
top++;
Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;
mg[i][j]=-1;
}
else
{mg[Stack[top].i][Stack[top].j]=0;
 top--;
}
} 
printf("没有路径:");
system("pause");
return 0;
}