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
*/