本文共 2740 字，大约阅读时间需要 9 分钟。

为了解决这个问题，我们需要找到从起点到终点的最小跳跃次数。跳跃规则是只能从同一行或者同一列的下一行跃过去。我们可以使用广度优先搜索（BFS）来解决这个问题，因为BFS适合寻找最短路径的问题。

方法思路

解决代码

#include 
   
    
using namespace std;
typedef long long ll;
queue
    
      q;
int tot = 0, s = -1, z = -1;
int head[100010], dis[100010];
struct ban { int l, r, p, y; } a[100010];
struct ty { int next, t; } edge[2000010];
void bfs() {
    dis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i != -1; i = edge[i].next) {
            int y = edge[i].t;
            if (dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
}
bool cmp(const ban &a, const ban &b) {
    if (a.y != b.y) return a.y < b.y;
    return a.l < b.l;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i].y = 0, a[i].l = 0, a[i].r = 0;
        cin >> a[i].y >> a[i].l >> a[i].r;
        a[i].p = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        cout << a[i].p << " ";
    }
    int l = 1, r = 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i].y == a[i + 1].y && a[i].r == a[i + 1].l) {
            edge[tot].next = head[i];
            edge[tot].t = i;
            head[i] = tot++;
            edge[tot].next = head[i + 1];
            edge[tot].t = i + 1;
            head[i + 1] = tot++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int current_y = a[i].y;
        int current_l = a[i].l;
        int current_r = a[i].r;
        l = max(current_l, 1);
        r = current_r;
        while (l <= r) {
            if (a[l].y != current_y) {
                l++;
                continue;
            }
            if (a[l].l > current_r) {
                break;
            }
            if (a[l].r < current_l) {
                l++;
                continue;
            }
            edge[tot].next = head[i];
            edge[tot].t = l;
            head[i] = tot++;
            edge[tot].next = head[i];
            edge[tot].t = r;
            head[i] = tot++;
        }
        if (l > 1) l--;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i].p == n) {
            s = i;
            z = i;
        }
    }
    bfs();
    cout << dis[z] - 1 << endl;
}
    
   

代码解释

转载地址：http://qpxwz.baihongyu.com/