前言:
今日打只狼打得吐血了，直接把它给卸载了，然后狠狠地复习了一下深度优先的算法、
so现在让我来分享一下深度优先搜索也就是dfs
概述:
深度优先搜索可以理解为一个栈，一直遍历一条路径，直至终点才将这个栈释放，再用栈存储其他路径。
同时该算法和bfs（广度优先搜索）一样只能用于权重一样的题目中，而出现只有大小不一的正权边优先使用Dijksra，含有负权边使用bell ford。
当dfs到达一条终点后它便会回溯，找其他的路径，不断地比较，找到最优解。但值得注意的是深度优先搜素不具有最短性
只有广度优先搜索才具有最短性（即访问最近的点才能具有最短性）。现在让我用例题了解一下深度优先搜索的搜索方式以及回溯过程
#实践:
给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
using namespace std;
const int N=1e4,M=1e4;
int g[N][M];
int bx,by,fx,fy;
bool st[N][M];//用来记录一条路径中该点是否走过
int n,m,t;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1,};//表示一点上下左右四个方向移动，避免四个循环重复，增加代码可读性
int cnt;//记录多少中情况
void dfs(int bx,int by){
if(bx==fx&&by==fy){
cnt++;//当有一条路径走到终点，种类数加1
return ;
}
for(int k=0;k<=3;k++){
int tx=bx+dx[k],ty=by+dy[k];
if(!st[bx+dx[k]][by+dy[k]]&&g[tx][ty]==1){
st[bx][by]=true;
dfs(tx,ty);
st[bx][by]=false;//这便是回溯
}
}
}
int main(){
cin>>n>>m>>t;
cin>>bx>>by>>fx>>fy;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
g[i][j]=1;//绘图
}
}
while(t--){
int x, y;
cin>>x>>y;
g[x][y]=0;//设置障碍
}
dfs(bx,by);
cout<<cnt;
return 0;
}
|
