本文共 2653 字，大约阅读时间需要 8 分钟。
为了解决这个问题，我们需要找到从起点到终点的最小跳跃次数。跳跃规则是只能从同一行或者同一列的下一行跃过去。我们可以使用广度优先搜索（BFS）来解决这个问题，因为BFS适合寻找最短路径的问题。
#includeusing 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/