因为此题数据范围较小,有dfs及bfs等多种做法。
DFS
比较正常的dfs,注意vis数组一定要回溯,不然会漏情况
例如这个数据
11 1 5
1 5 20 1 20 20 3 20 20 1 7
有无回溯vis数组结果不一样
代码:
#include <iostream>
using namespace std;
typedef long long ll;
int n, a, b, minn = 0x7fffffff;
int A[300], vis[300];//vis数组用来标记所走过的楼层
void dfs(int num, int step)
{
if (num == b)
{
minn = min(minn, step);
return;
}
if (num > n || num < 1)
return;
if (!vis[num] && step < minn)
{
vis[num] = 1;
dfs(num + A[num], step + 1);
dfs(num - A[num], step + 1);
vis[num] = 0;//回溯vis数组
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i)
{
cin >> A[i];
}
dfs(a, 0);
if (minn != 0x7fffffff)
cout << minn << endl;
else
cout << -1 << endl;
return 0;
}
BFS
由于要同时记录楼层和步数,所以选择在queue里套一个pair,用结构体也是可以的,但pair比较短
用pair定义起来方便,但用起来其实没有结构体方便。。。
代码:
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
queue<pair<int, int>> q;
int A[300], vis[300];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, a, b;
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i)
{
cin >> A[i];
}
q.push(make_pair(a, 0));
vis[a] = 1;
int f = 0;
while (!q.empty())
{
int num = q.front().first, step = q.front().second;
if (num == b)
{
f = 1;
break;
}
q.pop();
if (num + A[num] <= n && !vis[num + A[num]])
{
vis[num + A[num]] = 1;
q.push(make_pair(num + A[num], step + 1));
}
if (num - A[num] >= 1 && !vis[num - A[num]])
{
vis[num - A[num]] = 1;
q.push(make_pair(num - A[num], step + 1));
}
}
if (f)
cout << q.front().second << endl;
else
cout << -1 << endl;
return 0;
}