这是数据结构书上的一道例题,很多人都不陌生吧.
#include<stdio.h>
#define M 8
#define N 8
#define MaxSize 500
int mg[M+2][N+2]=
{
    {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,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};
int mgpath(int xi,int yi,int xe,int ye)       /*求解路径为:(xi,yi)->(xe,ye)*/
{
    struct
    {
        int i;                                    /*当前方块的行号*/
        int j;                                    /*当前方块的列号*/
        int di;                                   /*di是下一可走相邻方位的方位号*/
    }st[MaxSize];                                 /*定义栈*/
    int top=-1;                                   /*初始化栈地址*/
    int i,j,k,di,find;                        
    top++;                                        /*初始方块即入口进栈*/
    st[top].i=xi;st[top].j=yi;
    st[top].di=-1;mg[1][1]=-1;
    while(top>-1)                                 /*栈不为空时循环*/
    {
        i=st[top].i;j=st[top].j;di=st[top].di;    /*取栈顶方块*/
        if(i==xe&&j==ye)                          /*找到了出口,输出路径*/
        {
            printf("The Route is:\n");
            for(k=0;k<=top;k++)
            {
                printf("\t(%d,%d)",st[k].i,st[k].j);
                if((k+1)%5==0)                    /*每输出5个方块后换一行*/
                    printf("\n");
            }
            printf("\n");
            return (1);                           /*找到一条路径后返回1*/
        }
        find=0;
        while(di<4&&find==0)                      /*找(i,j)方块的下一个可走方块*/
        {
            di++;                                 /*找下一个方位*/
            switch(di)
            {
                case 0: i=st[top].i-1;j=st[top].j;break;
                case 1: i=st[top].i;j=st[top].j+1;break;
                case 2: i=st[top].i+1;j=st[top].j;break;
                case 3: i=st[top].i;j=st[top].j-1;break;
                default:break;
            }
            if(mg[i][j]==0)                       /*找到下一个可走相邻方块*/
                find=1;
        }
        if(find==1)                               /*找到了下一个可走相邻方块*/
        {
            st[top].di=di;                        /*修改原栈顶元素的di值*/
            top++;                                /*将可走的相邻方块进栈*/
            st[top].i=i;st[top].j=j;st[top].di=-1;
            mg[i][j]=-1;                          /*避免重复走到该方块,将其置为1*/
        }
        else                                      /*没有相邻方块可走,则退栈*/
        {
            mg[st[top].i][st[top].j]=0;           /*让该位置变为其他路径可走方块=1也行啊?*/
            top--;                                /*将该方块退栈*/
        }
    }
    return (0);                                   /*表示没有可走路径,返回0*/
}
int main()
{
    mgpath(1,1,M,N);
    getch();
}
书上只打印出了一条路线,现在要打印所有路径.把函数mgpath类型改为void,去掉return会打印出168种结果．我知道偶次的时候跟前面一次的路径相同,但是他们在出口行多了个向左拐的过程,在退栈,所以表面上看是一样的.
    我想出了两种方法:
#include<stdio.h>
#define M 8
#define N 8
#define MaxSize 500
int mg[M+2][N+2]=
{
    {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,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,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;  
}st[MaxSize]; 
int Ntd=1,top=-1;  
void print()
{
    int k;
    printf("The %dth Route is:\n",Ntd);
    for(k=0;k<=top;k++)
    {
        printf("(%d,%d)\t",st[k].i,st[k].j);
        if((k+1)%5==0)
            printf("\n");
    }
    printf("\n");
    Ntd++;    
}
void mgpath(int xi,int yi,int xe,int ye) 
{
    int i,j,k,find,di;
    top=0;            
    st[top].i=xi,st[top].j=yi,st[top].di=-1;
    mg[1][1]=-1;
    while(top>-1)     
        {
        i=st[top].i,j=st[top].j,di=st[top].di;  
        if(i==xe&&j==ye)                        
        {
            if(find==1)/*方法一:插入一句*/
                print();            
        }
        find=0;
        while(di<4&&find==0)
        {
            di++;
            switch(di)
            {
                case 1:i=st[top].i-1,j=st[top].j;break;
                case 2:i=st[top].i,j=st[top].j+1;break;
                case 3:i=st[top].i+1,j=st[top].j;break;
                case 4:i=st[top].i,j=st[top].j-1;break;
                default:break;
            }
            if(mg[i][j]==0)   
                find=1;
        }
        if(find==1)          
        {
            st[top].di=di;    
            top++;           
            st[top].i=i;st[top].j=j;st[top].di=-1;
            mg[i][j]=-1;              
        }
        else
        {
            /*if(st[top-1].i==xe&&st[top-1].j==ye)
            {方法2:插入这块代码
                mg[st[top].i][st[top].j]=1;
                top--;
                mg[st[top].i][st[top].j]=0;
                top--;
            }*/
            mg[st[top].i][st[top].j]=0;                                 top--;                   
        }
    }
}
int main()
{
    mgpath(1,1,M,N);
    getch();
    return 0;
}
方法1:在输出前判断,只有前进到出口才算,撤退到出口会与前面的路径重复就不打印出了*/
方法2:如果撤退到出口,则连出口一起弹出,封锁这个位置(这里是mg[8,7])省了后面来回.
最后的结果居然不同?一个是84,一个是80.方法1更有生存力,不过我很难找到方法2的错误!我表达的不太清楚,看到这帖的希望有兴趣帮下忙.