利用深度策略解决迷宫问题

叁歲伎倆 2022-12-18 05:55 107阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center 1]

1.数组derection\[8\]\[2\]=\{ \{0,1\},\{1,1\},\{1,0\},\{1,-1\},\{0,-1\},\{-1,-1\},\{-1,0\},\{-1,1\}\};表示八个方向，接下来会按正东方向按顺时针进行查找。  
例如从当前位置(1,2)向南查找则：  
g=x+direction\[2\]\[0\]=1+1=2;  
h=y+direction\[2\]\[0\]=2+0=2;  
2.两个栈LinkStackX和LinkStackY分别存放行坐标和列坐标。  
3.mark\[i\]\[j\]用于设置标志位，当mark\[i\]\[j\]=1时，表示该位置已被探索过。  
基本思路：  
①创建两个空栈StackX和StackY。  
②将入口entrtyX和entryY分别压入栈StackX和StackY。  
③当栈不空，取栈顶元素，出栈，当前位置为栈顶元素。  
④当mov<8,即还存在探索的方向。  
a.按照顺时针依次探索各个位置（posX,posY）。  
b.如果(posX，posY)是出口，输出路径，返回1。  
c.如果（posX，posY）时没有走过的通路；  
~设置标志位mark\[posX\]\[posY\]=1。  
~当前位置进栈。  
~将（posX,posY）设置为当前位置。  
设置mov=0。  
d.否则mov++

#include <stdio.h>
    #include <stdlib.h>
    
    struct MAZE_STRU
    { 
        int size;
        int **data;
    };
    typedef struct MAZE_STRU Maze;
    typedef int DataType;
    struct Node
    { 
        DataType data;
        struct Node*next;
    };
    typedef struct Node*PNode;
    typedef struct Node*top,*LinkStack;
    LinkStack SetNullStack_Link()
    { 
        LinkStack top=(LinkStack)malloc(sizeof(struct Node));
        if(top!=NULL)
        { 
            top->next=NULL;
        }
        else
        { 
            printf("alloc failure");
        }
        return top;
    }
    void Push_Link(LinkStack top,DataType x)
    { 
        PNode p=(PNode)malloc(sizeof(struct Node));
        if(p==NULL)
        { 
            printf("alloc failure");
        }
        else
        { 
            p->data=x;
            p->next=top->next;
            top->next=p;
        }
    }
    int IsNullStack_Link(LinkStack top)
    { 
        if(top->next==NULL)
            return 1;
        else
            return 0;
    }
    void Pop_Link(LinkStack top)
    { 
        PNode p;
        if(top->next==NULL)
            printf("it is empty stack!");
        else
        { 
            p=top->next;
            top->next=p->next;
            free(p);
        }
    }
    DataType Top_Link(LinkStack top)
    { 
        if(IsNullStack_Link(top)==1)
            printf("it is empty stack!");
        else
        { 
            return top->next->data;
        }
    }
    Maze* InitMaze(int size)
    { 
        int i;
        Maze*maze=(Maze*)malloc(sizeof(Maze));
        maze->size=size;
        maze->data=(int **)malloc(sizeof(int*)*maze->size);
        for(i=0;i<maze->size;i++)
        { 
            maze->data[i]=(int*)malloc(sizeof(int)*maze->size);
        }
        return maze;
    }
    void ReadMaze(Maze* maze)
    {    int i,j;
        for(i=0;i<maze->size;i++)
        { 
    
            for(j=0;j<maze->size;j++)
            scanf("%d",&maze->data[i][j]);
        }
    }
    void WriteMaze(Maze* maze)
    { 
        int i,j;
        printf("迷宫的结构如下：\n");
        for(i=0;i<maze->size;i++)
        { 
            for(j=0;j<maze->size;j++)
            { 
                printf("%5d",maze->data[i][j]);
            }
            printf("\n");
    
        }
    }
    int MazeDFD(int entryX,int entryY,int exitX,int exitY,Maze *maze)
    { 
        int derection[8][2]={ { 0,1},{ 1,1},{ 1,0},{ 1,-1},{ 0,-1},{ -1,-1},{ -1,0},{ -1,1}};
        LinkStack LinkStackX=NULL;
        LinkStack LinkStackY=NULL;
        int posX,posY;//临时变量，存放点坐标（x，y）
        int preposX,preposY;
        int **mark;//标记二维数组，标记哪些点走过，不在重复走
        int i,j;//循环变量
        int mov;//移动的方向
        //给标记的二维数组分配空间，并附初值
        mark=(int**)malloc(sizeof(int*)*maze->size);
        //给所有元素设置初值
        for(i=0;i<maze->size;i++)
            mark[i]=(int*)malloc(sizeof(int)*maze->size);
        for(i=0;i<maze->size;i++)
        { 
            for(j=0;j<maze->size;j++)
            mark[i][j]=0;
        }
        LinkStackX=SetNullStack_Link();//初始化栈
         LinkStackY=SetNullStack_Link();//初始化栈
         mark[entryX][entryY]=1;//入口点设置标志位
         Push_Link(LinkStackX,entryX);//入口点入栈
         Push_Link(LinkStackY,entryY);//入口点入栈
         while(!IsNullStack_Link(LinkStackX))
         { 
             preposX=Top_Link(LinkStackX);
             preposY=Top_Link(LinkStackY);
             Pop_Link(LinkStackX);
             Pop_Link(LinkStackY);
             mov=0;
             while(mov<8)
             { 
                 posX=preposX+derection[mov][0];
                 posY=preposY+derection[mov][1];
                 if(posX==exitX&&posY==exitY)
                 { 
                     Push_Link(LinkStackX,preposX);//出口点入栈
                     Push_Link(LinkStackY,preposY);//出口点入栈
                     printf("深度搜索迷宫的路径如下：\n");
                     printf("%d %d;",exitX,exitY);//打印出口点
                     while(!IsNullStack_Link(LinkStackX))//将路径逆序输出
                     { 
                         posX=Top_Link(LinkStackX);//取栈顶元素
                         posY=Top_Link(LinkStackY);//取栈顶元素
                         printf("%d %d;",posX,posY);//出栈
                         Pop_Link(LinkStackX);//出栈
                         Pop_Link(LinkStackY);//输出栈顶元素
                     }
                     return 1;
                 }
                 //还有路可以走
                 if(maze->data[posX][posY]!=1&&mark[posX][posY]!=1)
                 { 
                     mark[posX][posY]=1;
                     Push_Link(LinkStackX,preposX);//入栈
                     Push_Link(LinkStackY,preposY);//入栈
                     preposX=posX;
                     preposY=posY;
                     mov=0;//已经往前走了，因此重新开始从零号方向开始搜索
                 }
                 else
                    mov++;
    
             }
    
         }
    return 0;
    }
    int main()
    { 
        Maze* maze;
        int mazeSize;
        int entryX,entryY,exitX,exitY;
        int find=0;
        scanf("%d",&mazeSize);
        maze=InitMaze(mazeSize);
        ReadMaze(maze);
        scanf("%d%d%d%d",&entryX,&entryY,&exitX,&exitY);
        find=MazeDFD(entryX,entryY,exitX,exitY,maze);
        if(find==0)
            printf("找不到路径！");
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/dc25ad8576c54cc0a7b0076b3b45c891.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/e20c8529c29b46049691aa36f7aa3aa3.png