迷宫问题一、实验目的掌握采用深度优先策略求解迷宫问题二、实验内容本实验解决陷入迷宫的老鼠如何找到出口的问题，老鼠希望尝试所有的路径之后走出迷宫，如果它到达一个死胡同，将原路返回到上一个位置，尝试新的路径。

在每个位置上老鼠可以向8个方向运动，即东、南、西、北、东南、东北、西南、西北。

无论离出口多远，它总是按照这样的顺序尝试，当到达一个死胡同之后，老鼠将进行“回溯”，迷宫只有一个入口、一个出口，设计程序输出迷宫的一条通路，实验内容如下：（1）设计迷宫的存储结构；（2）采用回溯法设计求解通路的算法，利用栈实现回溯算法。

迷宫如下：Enter-> 0 1 1 1 0 0 0 0 0 00 0 0 1 0 0 0 1 0 00 1 0 1 1 0 0 1 0 00 1 0 0 1 0 1 1 0 00 1 0 0 1 0 1 1 0 01 1 1 0 1 0 1 0 0 00 0 1 0 0 0 1 0 1 10 0 1 0 0 0 1 0 1 10 1 1 0 1 0 1 0 0 00 0 0 0 1 0 1 1 0 0 --> EXIT下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！）Path: ( maze[0][0], maze[1][0], maze[1][1], maze[1][2], maze[2][2],maze[3][2], maze[3][3], maze[4][3], maze[5][3], maze[6][3],maze[6][4], maze[6][5], maze[5][5], maze[4][5], maze[3][5],maze[2][5], maze[2][6], maze[1][6], maze[0][6], maze[0][7],maze[0][8], maze[1][8], maze[2][8], maze[3][8], maze[4][8],maze[5][8], maze[5][7], maze[6][7], maze[7][7], maze[8][7],maze[8][8], maze[8][9], maze[9][9])Enter-> X 1 1 1 0 0 X---X---X 0X---X---X 1 0 0 X 1 X 00 1 X 1 1 X---X 1 X 00 1 X---X 1 X 1 1 X 00 1 0 X 1 X 1 1 X 01 1 1 X 1 X 1 X---X 00 0 1 X---X---X 1 X 1 10 0 1 0 0 0 1 X 1 10 1 1 0 1 0 1 X-- X-- X0 0 0 0 1 0 1 1 0 X --> EXIT1、提示：（1）数据结构：✧用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。

（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代码时简单些，而且让迷宫周围都是墙，防止错误的走出去）✧用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。

（用MARK[m+2][n+2]而不用MARK[m][n]的原因在于想表示和编写代码的时简单些）✧二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。

这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路✧用栈保存走过的路径（2）输出：✧迷宫布局，用0表示可以走通的地方，用1表示墙✧如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通✧带有路径的迷宫布局2、非递归算法Path(MAZE, MARK, m, n, MOVE, STACK)//A binary matrix MAZE(0:m+1,0:n+1) holds the maze.//STACK(mn,2) records the path{MARK(1,1)=1;STACK.push((1,1,1));While not STACK.empty(){(i,j,mov) = STACK.top();STACK.pop();While mov!=8{g=i+MOVE(mov,1);h=j+MOVE(mov,2);if g=m and h=n{reverseprint STACK;printi,j;printm,n;return;}if MAZE(g,h)=0 and MARK(g,h)=0{MARK(g,h)=1;STACK.push((i,j,mov));i=g;j=h;mov=0;}elsemov=mov+1;}}print “No path has been found”}附录：STL中栈的使用#pragma warning(disable:4786)#include <stack>#include <iostream>using namespace std ;typedef stack<int> STACK_INT;int main(){STACK_INT stack1;cout<< "stack1.empty() returned " <<(stack1.empty()? "true": "false") <<endl; // Function 3cout<< "stack1.push(2)" <<endl;stack1.push(2);if (!stack1.empty()) // Function 3 cout<< "stack1.top() returned " <<stack1.top() <<endl; // Function 1cout<< "stack1.push(5)" <<endl;stack1.push(5);if (!stack1.empty()) // Function 3 cout<< "stack1.top() returned " <<stack1.top() <<endl; // Function 1cout<< "stack1.push(11)" <<endl;stack1.push(11);if (!stack1.empty()) // Function 3 cout<< "stack1.top() returned " <<stack1.top() <<endl; // Function 1// Modify the top item. Set it to 6.if (!stack1.empty()) { // Function 3 cout<< "stack1.top()=6;" <<endl;stack1.top()=6; // Function 1 }// Repeat until stack is emptywhile (!stack1.empty()) { // Function 3 constint& t=stack1.top(); // Function 2 cout<< "stack1.top() returned " << t <<endl;cout<< "stack1.pop()" <<endl;stack1.pop();}}运行结果：stack1.empty() returned truestack1.push(2)stack1.top() returned 2stack1.push(5)stack1.top() returned 5stack1.push(11)stack1.top() returned 11stack1.top()=6;stack1.top() returned 6stack1.pop()stack1.top() returned 5stack1.pop()stack1.top() returned 2stack1.pop()三、实验代码LinkStack.h#ifndef LINKSTACK_H#define LINKSTACK_Htypedef int DataType;struct Node{DataType data;struct Node* next;};typedef struct Node *PNode;typedef struct Node *LinkStack;LinkStack SetNullStack_Link();int IsNullStack_link(LinkStack top);void Puch_link(LinkStack top,DataType x);void Pop_link(LinkStack top);DataType Top_link(LinkStack top);#endifLinkStack.c#include<stdio.h>#include<stdlib.h>#include"LinkStack.h"LinkStack SetNullStack_Link(){LinkStack top=(LinkStack)malloc(sizeof(struct Node));if(top!=NULL)top->next=NULL;elseprintf("Alloc failure");return top;}int IsNullStack_link(LinkStack top){if(top->next==NULL)return 1;elsereturn 0;}void Push_link(LinkStack top,DataType x){PNode p;p=(PNode)malloc(sizeof(struct Node));if(p==NULL)printf("Alloc failure");else{p->data=x;p->next=top->next;top->next=p;}}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(top->next==NULL){printf("It is empty stack!");return 0;}elsereturn top->next->data;}MazeDFS.c#include<stdio.h>#include<stdlib.h>#include"mazeutil.h"#include"LinkStack.h"int MazeDFS(int entryX,int entryY,int exitX,int exitY,Maze* maze){int direction[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;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=1;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+direction[mov][0];posY=preposY+direction[mov][1];if(posX==exitX&&posY==exitY){Push_link(linkStackX,preposX);Push_link(linkStackY,preposY);printf("\n深度探索迷宫路径如下：");printf("%d %d\n",posX,posY);while(!IsNullStack_link(linkStackX)){posX=Top_link(linkStackX);posY=Top_link(linkStackY);Pop_link(linkStackX);Pop_link(linkStackY);printf("%d %d\n",posX,posY);}return 1;}if(maze->data[posX][posY]==0&&mark[posX][posY]==0){mark[posX][posY]=1;Push_link(linkStackX,preposX);Push_link(linkStackY,preposY);preposX=posX;preposY=posY;mov=0;}elsemov++;}}return 0;}Main.c#include<stdio.h>#include"mazeutil.h"int main(void){Maze *maze;int mazeSize;int entryX,entryY,exitX,exitY;int find=0;printf("请输入迷宫大小：");scanf_s("%d",&mazeSize);entryX=0;entryY=0;exitX=mazeSize-1;exitY=exitX;maze=InitMaze(mazeSize);ReadMaze(maze);printf("输入的迷宫结构如下：\n");printf("请输入迷宫的入口x.y,出口x,y\n");scanf_s("%d%d%d%d",&entryX,&entryY,&exitX,&exitY);find=MazeDFS(entryX,entryY,exitX,exitY,maze);if(!find){printf("找不到路径！\n");}return 0;}Mazeutil.c#include<stdio.h>#include<stdlib.h>#include"mazeutil.h"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;printf("请用矩阵的形式输入迷宫的结构：\n");for(i=0;i<maze->size;i++){for(j=0;j<maze->size;j++)scanf_s("%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");}}Mazeutiil.h#ifndef MAZE_H#define MAZE_Htypedef struct MAZE_STRU{int size;int **data;}Maze;Maze* InitMaze(int size);void ReadMaze(Maze *maze);void WriteMaze(Maze *maze);int MazeBFS(int entryX,int entryY,int exitX,int exitY,Maze* maze); int MazeDFS(int entryX,int entryY,int exitX,int exitY,Maze* maze); #endifNode.h#ifndef NODE_H#define NODE_Htypedef int DataType;struct NodeDataType data;struct Node* next;};typedef struct Node *PNode; #endif实验结果：四、实验总结。