深度优先搜索简要讲解（附带基础题）

PS:要放假了，考试也快考完了，时间多了起来，有空便来写一篇博客，接下来博客更新会快一点，Thanks for your watching。

前言：该博客主要通过题目讲解给大家简要的介绍一下

题目链接：P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目：

 

题目思路：

简单的dfs

对原来的地方进行标记

并向下一个地方进行转移

每次更新步数最小值

注：

大家只要记住dfs的几个基础模板

很容易学会

dfs的注意点：

1.设定一个标记数组 vis[ ](注意标注的位置，使其不会影响到余下的情况)

2.dfs的设定一个要求的值（一般取能取的范围的最大）并在，满足其他的条件下不断的刷新它

3.弄清楚进行dfs操作后的状态、

代码详解：

#include<stdio.h>
#include<iostream>
using namespace std;
long long arr[206];
int vis[206];
int minn = 999999999;
int n, a, b;
void dfs(int step,int sum)
{
	if (step == b)//如果到达该楼层，更新到达目标楼层的最少步数
	{
		minn = min(minn, sum);
	}
	vis[step] = 1;//对该位置进行标记，防止下次再走到该位置（优化）
	if (step + arr[step] <= n && sum < minn&&vis[step + arr[step]] != 1) {
		dfs(step + arr[step], sum + 1);
	}
	if (step - arr[step] >= 1 && sum < minn && vis[step - arr[step]] != 1) {
		dfs(step - arr[step], sum + 1);
	} 
	vis[step] = 0;
}
int main()
{
	cin >> n>>a>>b;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &arr[i]);
	}//存楼梯能往上下走的步数
	if (a != b)//如果一开始不在要到的楼层
	{
		dfs(a, 0);
		if (minn != 999999999)
			cout << minn;
		else
			cout << -1;
	}
	else cout << 0;
	return 0;
}

PS:十年磨一剑，霜刃未曾试