【DFS与BFS】洛谷 P1135 奇怪的电梯

题目:奇怪的电梯 - 洛谷 (luogu.com.cn)

因为此题数据范围较小,有dfs及bfs等多种做法。

DFS

比较正常的dfs,注意vis数组一定要回溯,不然会漏情况

例如这个数据

11 1 5

1 5 20 1 20 20 3 20 20 1 7

有无回溯vis数组结果不一样

【DFS与BFS】洛谷 P1135 奇怪的电梯

【DFS与BFS】洛谷 P1135 奇怪的电梯

代码:

#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;
}
上一篇:显示Mac电脑下的隐藏文件


下一篇:根据传入的文件名称动态从moglifs图片服务器拿到pdf文档并在线浏览