1.实验目的：
（1）掌握回溯算法；
（2）掌握图的深度优先和广度优先搜索算法并用来解决实际问题；
2. 实验内容：
迷宫求解：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求如下：
（1）首先实现一个栈类型，利用回溯法求解迷宫路径（非递归程序）。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。
（2）建立图的存储结构，利用深度优先搜索，求得迷宫路径。输出方式自行定义，简单清晰则可。
（3）利用广度优先搜索，求得迷宫路径。输出方式自行定义，简单清晰则可。
（4）假如有多条路径，如何求最短的那一条路径？
3.实验代码：
#include<bits/stdc++.h> using namespace std; int n,m; int mp[110][110]; struct node { int x,y; string dir; }; bool check(node t)///判断某个节点是否可以走 { int x=t.x,y=t.y; if(x>=1&&x<=n&&y>=1&&y<=m&&!mp[x][y]) return 1; return 0; } void init() { ///输入迷宫 cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>mp[i][j]; } void findpath1()///非递归求解迷宫路径 { stack<node>stk; node now= {1,1,"0"}; stk.push({1,1,"0"}); while(!stk.empty()) { node t=stk.top(); if(t.x==n&&t.y==m) { break; } node ne=t; mp[t.x][t.y]=2; ne=t; ne.x--; if(check(ne)) { t.dir="up"; stk.pop(); stk.push(t); stk.push(ne); continue; } ne=t; ne.x++; if(check(ne)) { t.dir="down"; stk.pop(); stk.push(t); stk.push(ne); continue; } ne=t; ne.y--; if(check(ne)) { t.dir="left"; stk.pop(); stk.push(t); stk.push(ne); continue; } ne=t; ne.y++; if(check(ne)) { t.dir="right"; stk.pop(); stk.push(t); stk.push(ne); continue; } t=stk.top(); stk.pop(); mp[t.x][t.y]=3; } vector<node>v; while(!stk.empty()) { v.push_back(stk.top()); stk.pop(); } reverse(v.begin(),v.end()); for(int i=0; i<v.size(); i++) cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].dir<<endl; } stack<node>path,tmp; int nx[]= {0,0,1,-1}; int ny[]= {1,-1,0,0}; int vis[110][110]; int cnt=0; void findpath2(int x,int y) ///dfs求解迷宫所有路径 { if(x==n&&y==m) { cout<<"***************路径"<<++cnt<<"*****************"<<endl; while(!path.empty()) { tmp.push(path.top()); path.pop(); } while(!tmp.empty()) { cout<<"("<<tmp.top().x<<","<<tmp.top().y<<")"<<endl; path.push(tmp.top()); tmp.pop(); } return ; } if(x<1||x>n||y<1||y>m) return ; for(int i=0; i<4; i++) { int xx=x+nx[i],yy=y+ny[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!mp[xx][yy]&&vis[xx][yy]==0) { vis[xx][yy]=1; path.push({xx,yy}); findpath2(xx,yy); vis[xx][yy]=0; path.pop(); } } } queue<node>q; int dis[110][110],fx[110][110],fy[110][110]; void Prinpath3(int x,int y)///bfs打印路径 递归打印 { if(x!=-1&&y!=-1) { Prinpath3(fx[x][y],fy[x][y]); cout<<"("<<x<<","<<y<<")"<<endl; } } void findpath3()///bfs求解最短路径 { memset(dis,-1,sizeof dis);///初始化距离数组 q.push({1,1});///将起始点放入队列 dis[1][1]=0;///初始化距离 fx[1][1]=fy[1][1]=-1;///表示这个点的上一个点的坐标 while(!q.empty()) { node now=q.front(); q.pop(); for(int i=0; i<4; i++) { node nex; nex.x=now.x+nx[i],nex.y=now.y+ny[i]; if(check(nex)&&dis[nex.x][nex.y]==-1) { q.push(nex); dis[nex.x][nex.y]=dis[now.x][now.y]+1; fx[nex.x][nex.y]=now.x; fy[nex.x][nex.y]=now.y; } } } Prinpath3(n,m); } int main() { init(); //findpath1(); // findpath2(1,1); findpath3(); return 0; } /* 3 3 0 1 1 0 1 1 0 0 0 */
