Brief explanation of depth first search (with basic questions)

PS: It's time for a holiday , The exam is almost over , More time , Come and write a blog when you are free , Next, blog updates will be faster ,Thanks for your watching.

Preface ： This blog mainly gives you a brief introduction through topic explanation

Topic link ：P1135 Strange elevator - Luogu | New ecology of computer science education (luogu.com.cn)

subject ：

 

Topic ideas ：

ordinary dfs

Mark the original place

And move to the next place

Minimum number of steps per update

notes ：

Just remember dfs Several basic templates

It's easy to learn

dfs Points for attention ：

1. Set an array of tags vis[ ]( Pay attention to the marked position , So that it will not affect the rest of the situation )

2.dfs Set a required value （ Generally, the maximum range that can be taken ） And in , Meet other conditions and constantly refresh it

3. Make sure to proceed dfs Status after operation 、

Code details ：

#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)// If you arrive at this floor , Update the minimum number of steps to reach the target floor 
	{
		minn = min(minn, sum);
	}
	vis[step] = 1;// Mark this position , Avoid going to this position next time （ Optimize ）
	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]);
	}// Save the steps that the stairs can go up and down 
	if (a != b)// If you are not on the floor to be reached at the beginning 
	{
		dfs(a, 0);
		if (minn != 999999999)
			cout << minn;
		else
			cout << -1;
	}
	else cout << 0;
	return 0;
}

PS: Ten years to sharpen a sword , Frost blade never tried