DFS走迷宫有多少条路的问题

题目是这样的：

img


现在我不考虑打印路径只计算有多少种路径，为什么总是和答案不太一样？
我的代码是这样的：

#include
#include 
char map[5][3];                       //一般用二维数组处理迷宫的样子 
int d[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //这个二维数组用于处理，左、上、右、下。左上角坐标是(0, 0)
int sum=0;
int sx,sy,tx,ty;   //有s的是指起点，有t的是指终点 
void dfs(int x,int y);

int main()
{   
    int i,j,x,y;
//读入迷宫 
    for(i=0;i<5;i++)
       {
           for(j=0;j<3;j++)
               {
                   scanf("%c",&map[i][j]);
                   if(map[i][j]=='@') //找起点(不用另起，只需要在读入迷宫的时候，顺带找)
                    sx=i,sy=j;
                   if(map[i][j]=='*')//找终点
                      tx=i,ty=j;
                   getchar();                //用来清楚缓存 
               }
       }
dfs(sx,sy) ;
printf("总共有%d走法",sum);
 } 
void dfs(int x,int y)
{
    int nx,ny,i,cnt=0;     //nx表示新的x，ny表示新的y。 
//    int p_x[10],p_y[10];     //处理路径问题 ,路径我都记录下来，打不打印是我的事 
    for(i=0;i<4;i++)             //用循环和数组实现左上右下 
       {
           nx=x+d[i][0];
           ny=y+d[i][1];
           if(map[nx][ny]=='*')                               //写递归时可以先想想递归出口是什么 
             {
                 sum++;

            continue;               //和break不一样 ，走下一个方向 ,是最近的那个点再一次左上右下 
                 
           }
        else if(nx>4 || nx<0 || ny <0 || ny>2) //不在地图内 
               continue;
               
           else if(map[nx][ny]=='.')
            {

               map[nx][ny] = '#';     //保存现场。这个点在这次更深的dfs中不能再用,把其当作墙来看 
               //j++;
            dfs(nx,ny);
            map[nx][ny] = '.';     //恢复现场。回溯之后，这个点可以再次用   
        //    j--; 
            } 
       }
    
 }

代码运行结果如下：

img


答案是只有7种走法，现在我不考虑打印路径只计算有多少种路径，为什么我的是10种走法，哪里的思路和代码不太对？请指出，非常感谢。

你把所有的走法都输出一下，看看是不是和例子的不同，多了什么

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 你可以看下这个问题的回答https://ask.csdn.net/questions/1056955
  • 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：DFS算法解决迷宫路径生成上的应用
  • 除此之外, 这篇博客: DFS遍历迷宫输出所有路径（借助数据结构栈）中的 写在最后（更新） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

    为了方便大家，我这打出来一个直接复制粘贴就可以运行的代码👨‍🦳

    /* filename:  数据结构实验_迷宫.c
 * brife:	  Sovle the maze problem by using dfs&bfs
 * author:	  HP1020--SNOOHAIRY
 * date:	  2019.10.18 -- Firday
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 20

/*  *建立一个二维数组存迷宫
    *要是八个方向能有位置则压入栈，要是下一步没有则弹出栈回溯
    *直到找到终点为止
*/
int direction[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};  //定义一个数组存八个方向操作数
int maze[MAXN][MAXN];
int flag=0;

//栈中存位置以及遍历时所走的方向，打印时可以显示出来
typedef struct Node{
    int x;
    int y;
    //  int dir;           //-1为左上右下对应 '\' 0为上下对应'|'  1为左右对应'——' 2为左下右上对应'/'
    struct Node *next;
}Node;

typedef Node* Stack;     //定义数据结构栈 Stack

//-----------创建一个空栈--------------
Stack creakEmptyStack(){
    Stack p;
    p=(Stack)malloc(sizeof(Node));    //申请一个空间
    if(p){
        p->next=NULL;
        return p;
    }
    else{
        printf("No space!\n");    //申请空间失败则提示并返回空
        return NULL;
    }
}

//------------将元素压入栈----------------
void push(int x,int y,Stack s){
    Stack p;
    p=(Stack)malloc(sizeof(Node));
    if(p){                   //如果申请空间成功则用头插法将元素压入
        p->x=x;
        p->y=y;
        if(!s->next) p->next=NULL;  //如果此时栈里还没有任何元素，则p此时为第一个结点
        else p->next=s->next;  //否则将p插入头结点之后
        s->next=p;
    }
    else{
        printf("No space!\n");
    }
}

//-------------检测栈是否为空--------------
int isEmpty(Stack s){           //为空则返回1，不为空返回0
    if(s->next==NULL) return 1;
    else return 0;
}
//--------------将元素弹出栈----------------
void pop(Stack s){
    Stack p;
    p=s->next;
    if(p->next){
        s->next=p->next;
        free(p);
    }
    else return;
}
//------------取栈顶元素------------------
Node top(Stack s){
    Node t;
    //判断是否为空，若不为空则返回
    t=*(s->next);
    return t;
}

void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s);
void printPath(Stack s,int n,int m);
 
int main()
{
    int n,m,i,j,xa,xb,ya,yb,ox;
    //--------------建立迷宫--------------
    printf("请输入迷宫大小：（长、宽）\n");
    scanf("%d%d",&n,&m);
    if(n<=20&&m<=20){
        printf("请选择构建迷宫的方式：\n0.随机生成迷宫\n1.手动输入迷宫\n"); //实际上不是0就可以手动输入
        scanf("%d",&ox);
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(!ox)maze[i][j]=rand()%2;    //这里为伪随机数
                else scanf("%d",&maze[i][j]);
            }
        }
         printf("\n");
        //----------输出构建迷宫-------------
        printf("生成的迷宫如下：\n");
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                printf("%d  ",maze[i][j]);
            }
            printf("\n");
        }
 
        printf("请输入起点及终点：\n");
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        
        //标记起点
        maze[xa-1][ya-1]=2;                        
 
        //创建一个空栈
        Stack s=creakEmptyStack();
        //创建一个空队列
        //QueueLink q=creakEmptyQueue();
        mazePath(xa-1,ya-1,xb-1,yb-1,n,m,s);
        if(!flag) printf("没有成功找到路径\n");
    }
    else printf("输入数据超出迷宫范围\n");
}
 
//-----------遍历迷宫寻找路径(dfs)------------
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){
    int newx,newy,i;
    Node t;
    for(i=0;i<8;i++){
        newx=x+direction[i][0];
        newy=y+direction[i][1];
        if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){    //走到出口
            push(newx,newy,s);
            maze[newx][newy]=2;
            if(newx==endx&&newy==endy){
                flag++;
                printPath(s,n,m);
                maze[newx][newy]=0;
                pop(s);
            }
            else{
                mazePath(newx,newy,endx,endy,n,m,s);
            }
        }
//        else if(!isEmpty(s)) pop(s);
    }
    maze[x][y]=0;   //遍历完八个方向之后回溯前将自己赋为空
    pop(s);
}
 
//-------------打印迷宫路径-----------------
void printPath(Stack s,int n,int m){
    int cont =0;    //计算路径长度
    s=s->next;
    int i=0,j=0;
    printf("第%d条路径为：\n",flag);
    for(i=0;i<n;i++){                         //按图形输出
        for(j=0;j<m;j++){
            if(maze[i][j]==2) printf("*  ");
            else printf("%d  ",maze[i][j]);
        }
        printf("\n");
    }
    while(s->next){                          //将栈中的元素输出为直观路径
        printf("(%d,%d)->",s->x+1,s->y+1);
        s=s->next;
        cont++;
    }
    printf("(%d,%d)",s->x+1,s->y+1);
    cont++;
    printf("\n");
    printf("路径长度为：%d\n\n",cont);
}

    📢  转载请注明出处🎈 码字不易，能跑出想要的效果的话点个赞叭


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^