求组这题DFS应该怎么写
查看原帖
求组这题DFS应该怎么写
976912
BDCYI楼主2024/11/6 16:56
#include <bits/stdc++.h>
using namespace std;
int N, A, B;
vector<int> v;
vector<int> r;
int rmin = INT_MAX;
void dfs(int t)
{
	if (r[B] >= rmin)
		return;
	if (t == B)
	{
		rmin = min(rmin, r[B]);
		return;
	}
	if (t + v[t] > 0 && t + v[t] <= N && r[t + v[t]] == -1)
	{
		r[t + v[t]] = r[t] + 1;
		dfs(t + v[t]);
		r[t + v[t]] = -1;
	}
	if (t - v[t] > 0 && t - v[t] <= N && r[t - v[t]] == -1)
	{
		r[t - v[t]] = r[t] + 1;
		dfs(t - v[t]);
		r[t - v[t]] = -1;
	}	
}
int main()
{
	
	cin >> N >> A >> B;
	v.resize(N + 1, 0);
	for (int i = 1; i <= N; i++)
	{
		cin >> v[i];
	}
	r.resize(N + 1, -1);
	r[A] = 0;
	dfs(A);
	if (rmin != INT_MAX)
		cout << rmin;
	else
		cout << "-1";
}
2024/11/6 16:56
加载中...