题目:P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态
类型:搜索
dfs做法
1用例会TLE
注意要点
1.往上走 往下走 去深搜(判断是否能走)
2.是否已经访问这个节点(如果访问,则没有意义)剪枝1
3.当step<=ans 才有继续搜索的必要 剪枝2
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
int n, a, b, minn;
int k[N];
int is_vis[N]; //有没有去过
void search(int x, int step)
{
if (x == b)
{
minn = min(minn, step);
return;
}
else if (step <= minn) //只有比 minn小的 才有必要继续搜下去
{
is_vis[x] = 1; //来过
//往上走
//能往上 并且没有来过 如果来过 很有可能就死循环了
if (x + k[x] <= n && !is_vis[x + k[x]])
{
search(x + k[x], step + 1);
}
//往下走
if (x - k[x] >= 1 && !is_vis[x - k[x]])
{
search(x - k[x], step + 1);
}
is_vis[x] = 0; //回溯
}
}
int main ()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
cin >> k[i];
}
minn = INF, is_vis[a] = 1;
search(a, 0);
if (minn != INF)
cout << minn;
else
cout << "-1";
}
然后就
bfs做法
注意要点
入队列的时候就需要把节点 设置为访问
而不是在出的时候 不然会产生死循环
例如 3入队列了 但是刚刚出去的 是能到达3的 但是3还没有出 没有被标记上已经访问 就又回走回3
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
int a, b, n, ans = INF;
int k[N], is_vis[N];
typedef pair<int, int > PII; //first 当前所处楼层 second 到此楼层所用步数
queue<PII> q;
PII tmp;
void bfs(PII x)
{
q.push(x);
while (!q.empty())
{
tmp = q.front();
q.pop();
if (tmp.first == b)
{
ans = tmp.second;
break;
}
//往上走
//能走 且没有被访问过
if (tmp.first + k[tmp.first] <= n && ! is_vis[tmp.first + k[tmp.first]])
{
//入队
q.push(make_pair(tmp.first + k[tmp.first], tmp.second + 1));
is_vis[tmp.first + k[tmp.first]] = 1;
}
//往下走
//能走 且没有被访问过
if (tmp.first - k[tmp.first] <= n && ! is_vis[tmp.first - k[tmp.first]])
{
//入队
q.push(make_pair(tmp.first - k[tmp.first], tmp.second + 1));
is_vis[tmp.first - k[tmp.first]] = 1;
}
}
}
int main ()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
cin >> k[i];
}
is_vis[a] = 1;
bfs(make_pair(a, 0));
if (ans != INF)
cout << ans;
else
cout << "-1";
}