给一个不一样的题解，双向搜索！

题目分析

给定一个包含 n 个节点的图，每个节点编号从 1 到 n。对于每个节点 i，存在两条边：i + k 和 i - k，其中 k 是一个给定的整数。我们需要找到从节点 a 到节点 b 的最短路径。

解题思路

由于图的结构特殊，每条边都是节点加减 k，因此我们可以使用双向广度优先搜索（Bidirectional BFS）来找到最短路径。双向 BFS 从起点和终点同时开始搜索，当两者在某个节点相遇时，即找到了最短路径。

代码实现

1. 数据结构：

   • 使用两个邻接表 g1 和 g2 分别存储正向和反向的边。
   • 使用两个队列 q1 和 q2 分别存储正向和反向的 BFS 队列。
   • 使用两个哈希表 vis1 和 vis2 分别记录正向和反向访问过的节点及其步数。

2. BFS 搜索：

   • 同时从起点 a 和终点 b 开始搜索。
   • 每次从两个队列中分别取出一个节点，进行扩展。
   • 如果在扩展过程中，发现某个节点被另一方向的 BFS 访问过，则找到了最短路径。
   • 如果搜索完所有可能的路径仍未相遇，则输出 -1 表示无解。

3. 输入输出：

   • 输入包括节点数 n，起点 a，终点 b，以及边的变化量 k。
   • 输出从起点到终点的最短路径长度。

时间复杂度分析

代码的时间复杂度主要由广度优先搜索（BFS）决定：

1. 图的构建：

   • 构建图的时间复杂度为 O(n)，因为我们需要遍历每个节点，并为每个节点添加两条边（如果边存在）。

2. 双向 BFS：

   • 在最坏的情况下，双向 BFS 需要遍历整个图。由于每次扩展都会访问新的节点，因此时间复杂度取决于节点的访问次数。
   • 在双向 BFS 中，每次扩展的节点数最多为 2 * k，因为每个节点最多有两条边（一条是加 k，一条是减 k）。
   • 因此，双向 BFS 的时间复杂度为 O(n / k)，其中 n 是节点数，k 是边的变化量。

3. 总时间复杂度：

   • 总时间复杂度为 O(n + n / k) = O(n)。

综上所述，上述代码的时间复杂度为 O(n)。

代码注释

/*
 *  @filename:~/Documents/workspace/vscode_space
 *  @author: Ly_boy
 *  @date: 2024-11-27 08:38:36  星期三
 *  @version: V1.0.1
 *  @description: Copyright (cpp) 2024 by Ly_boy, All Rights Reserved.
 */
#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

int n, a, b, k;
vector<int> g1[205], g2[205];
queue<pair<int, int>> q1, q2;       // q1存正向，q2存反向
unordered_map<int, int> vis1, vis2; // vis1存正向，vis2存反向

void bfs()
{
    if (a == b)
    {
        cout << 0;
        return;
    }
    q1.push({a, 0});
    q2.push({b, 0});

    vis1[a] = 0;
    vis2[b] = 0;

    while (!q1.empty() || !q2.empty())
    {
        int size = q1.size();
        for (int i = 0; i < size; i++) // 正向
        {
            auto [x, step] = q1.front();
            q1.pop();
            for (auto y : g1[x])
            {
                if (vis1.find(y) == vis1.end()) // 如果没访问过
                {
                    if (vis2.find(y) != vis2.end()) // 如果反向访问过
                    {
                        printf("%d\n", step + 1 + vis2[y]);
                        return;
                    }
                    vis1[y] = step + 1;
                    q1.push({y, step + 1});
                }
            }
        }
        size = q2.size();
        for (int i = 0; i < size; i++) //  反向
        {
            auto [x, step] = q2.front();
            q2.pop();
            for (auto y : g2[x])
            {
                if (vis2.find(y) == vis2.end()) // 如果没访问过
                {
                    if (vis1.find(y) != vis1.end()) // 如果正向访问过
                    {
                        printf("%d\n", step + 1 + vis1[y]);
                        return;
                    }
                    vis2[y] = step + 1;
                    q2.push({y, step + 1});
                }
            }
        }
    }
    printf("-1\n");
}

int main()
{
    scanf("%d%d%d", &n, &a, &b); // n个点，a起点，b终点
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &k);
        int up = i + k, down = i - k;
        if (up <= n) // 正向存到g1，反向存到g2
        {
            g1[i].push_back(up);
            g2[up].push_back(i);
        }
        if (down >= 1)
        {
            g1[i].push_back(down);
            g2[down].push_back(i);
        }
    }
    bfs();
    return 0;
}