题解：P12322 [蓝桥杯 2024 国 Java C] 瞬移

· · 题解

思路

看到求最少步数自然的想到 bfs。

暴力 bfs，每走到一个点就 O(n^2) 的查找能走到哪些点，搜到终点时输出步数，总复杂度 O(n^3)，肯定是会炸掉的，考虑优化。

注意到每次都要进行一个 O(n^2) 的查找，考虑预处理，可以先 O(n^2) 的算出所有走的步数的方案，排序后去重，在搜索时就可以只遍历去重后的数组，就可以将 O(n^2) 的查找降到 O(l)，总复杂度为 O(n\times l)，就可以切掉了。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 4e6 + 5; 

int n,l,a[N],s,d[N],tot,cnt;

bool vis[N];

void bfs() {
    queue<pair<int,int> > q;     // first 是当前下标，second 是当前步数 
    q.push({1,0});          //初始下标为 1，步数为 0    
    while(!q.empty()) {
        int p = q.front().first;
        int step = q.front().second;
        q.pop();
        if(p == l) {          //如果到了 
            cout << step;     //输出步数 
            return;           //返回 
        }
        if(vis[p]) continue;  //走过了就跳过 
        vis[p] = true;        //标记走过 
        for(int i = 1;i<=cnt;i++) q.push({(d[i] + p - 1) % l + 1,step + 1});  //根据题目给的公式算出接下来会走到哪，步数加 1，入队 
    }
    cout << -1;         //不行就输出 -1 
}

int main() {
    cin >> n >> l;
    for(int i = 1;i<=n;i++) cin >> a[i];
    for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) d[++tot] = (a[i] + a[j]) % l;   //预处理可能走多少步 
    sort(d+1,d+1+tot);           //排序
    cnt = unique(d+1,d+1+tot) - d - 1;        //去重 
    bfs();
    return 0;
}

对你有帮助就点个赞吧 owo。