洛谷P1135 题解

代码上方文字的注释

1.时间复杂度

• dfs: O(2ⁿ)
• bfs: O(n)

2.题目类型

模拟、搜索

3.需要用到什么知识点

• dfs
• bfs

题目中的详细注释

DFS

思路：到了一层可以选择上或者下，dfs则上下每种选择都走一遍

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 210;
int n, a, b;
int k[N];
int dist[N];

void dfs(int u, int cnt){

    if(dist[u]<=cnt) return;
    dist[u] = cnt;

    if(u+k[u]<=n) dfs(u+k[u], cnt+1);
    if(u-k[u]>=1) dfs(u-k[u], cnt+1);

}

int main()
{
    memset(dist, 0x3f, sizeof dist);
    cin >> n >> a >> b;

    for(int i = 1; i <= n; i++){
        cin >> k[i];
    }

    dfs(a, 0);

    if(dist[b] == 0x3f3f3f3f)cout << -1;
    else cout << dist[b];

    return 0;
}

BFS

如果可以上/下，就入队，直到搜索到B层

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 210;
int n, a, b;
int k[N];
int dist[N];
bool st[N];
queue<int> q;

void bfs(){
    q.push(a);
    st[a] = 1;
    dist[a] = 0;
    while(q.size()){
        int t = q.front();
        q.pop();
        int up = t+k[t];
        int down = t-k[t];
        if(t == b) return;
        if(up<=n && !st[up]){
            st[up] = 1;
            q.push(up);
            dist[up] = dist[t]+1;
        }if(down>=1 && !st[down]){
            st[down] = 1;
            q.push(down);
            dist[down] = dist[t]+1;
        }
    }
}

int main()
{
    memset(dist, 0x3f, sizeof dist);
    cin >> n >> a >> b;

    for(int i = 1; i <= n; i++){
        cin >> k[i];
    }

    bfs();

    if(dist[b] == 0x3f3f3f3f)cout << -1;
    else cout << dist[b];

    return 0;
}

做题后的总结

目前得分 100分

• 进行大体修改2次（全部推翻重来）

• 共测试2次

• 共提交2次

• 本题正确(最优)解法：BFS

• 目前时间复杂度：50ms