题目

TUOJhttps://sim.csp.thusaac.com/contest/36/problem/3

思路参考：

出处是这个博客的评论区：CCF-CSP第36次认证第四题——跳房子【NA！巧妙利用BFS】_csp跳房子-CSDN博客

核心思路

BFS：通过队列逐层扩展，首次到达终点的路径即为最短跳跃次数。

剪枝：由于是从最远端（k[t.pos]）开始向近端尝试，如果某个跳跃点 t.pos + i 之前已经被其他路径访问过，那么比它更近的跳跃点（在之前的搜索中）也大概率被覆盖了

（从远到近遍历也是为了方便减枝）

那么有同学要问了，为什么vis数组记录 t.pos + i有没有访问过？vis记录最终落点行不行？（亲测不行，会有50%是WA）

这是因为存在回退 a[i]，使得最终落点有随机性（不单调）

在原始循环中，你尝试的跳跃目标是 Target=t.pos+i。当你从大到小遍历 i 时，Target是从右向左递减的。
但是，最终落点 FinalPos=Target−a[Target]并不是单调的。

• 跳得远的目标点，回退可能非常多；
• 跳得近的目标点，回退可能很少。

代码中break含义是：“既然这个点我访问过了，那么它左边的点我也没必要看了”。

如果vis 的是最终落点，举个例子：
假设你在位置 10，最大跳跃距离 k=2。

• 尝试 i=2（跳到 12）：假设 a[12]=10，最终落点是 2。如果位置 2 之前被访问过，触发 if(vis[2])。
• 由于触发了break，程序不再尝试 i=1（跳到 11）。
• 但如果 a[11]=0，最终落点是 11！位置 11 可能是一个全新的、离终点更近的点。
• 结果：你因为远端跳到了一个“旧地方”而直接放弃了近端可能跳到的“新地方”，导致根本搜不到正确路径。

代码

可以让AI总结一下代码逻辑

问题描述

• 有编号1~n的一排格子，从格子1出发，要到达格子n或更远

• 每个格子i有两个属性：

  • k[i]：从该格子最多可以向前跳的步数（可选1~k[i]步）

  • a[i]：跳到该格子后，会自动回退a[i]步

核心思路

1. BFS求最短路径

使用队列进行广度优先搜索，因为BFS逐层扩展的特性，第一次到达终点时的步数一定是最少的。

2. 状态表示

struct node {
    int pos;   // 当前所在的格子编号
    int step;  // 已经跳跃的次数
};

3. 跳跃规则

从位置t.pos出发：

• 可以向前跳i步（i从1到k[t.pos]）

• 跳到位置t.pos + i

• 然后因为回退机制，实际到达位置为：t.pos + i - a[t.pos + i]

4. 终点判断

如果t.pos + k[t.pos] >= n，说明从当前位置最多跳k步就能到终点，输出t.step + 1。

5. 剪枝优化

从i = k[t.pos]开始从大到小遍历：

• 如果t.pos + i已被访问过，直接break（因为更小的i对应的位置在之前的搜索中大概率也被覆盖了）

• 否则标记已访问，将实际落点入队

输出结果

• 如果能到达终点，输出最少跳跃次数

• 如果不能，输出-1

算法特点

• BFS保证最优解

• 从远到近遍历便于剪枝

• 实际位置需要考虑a数组的回退影响

/*
BFS
BFS通过队列逐层扩展，首次到达终点的路径即为最短跳跃次数。
剪枝思路：由于是从最远端（k[t.pos]）开始向近端尝试,
如果某个跳跃点 t.pos + i 之前已经被其他路径访问过，那么比它更近的跳跃点（在之前的搜索中）也大概率被覆盖了
从远到近遍历，方便减枝
*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+5;
int a[N],k[N],vis[N];
struct node{
	int pos, step; //当前位置：第pos个格子  步数 
};

void solve(){
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>k[i];
	
	queue<node>q;
	q.push({1,0}); //从第一个格子开始 0步
	while(!q.empty()){
		auto t=q.front(); q.pop();
		if(t.pos+k[t.pos]>=n){ //已经可以到第n个格子 
			cout<<t.step+1<<endl;
			return;
		}
		for(int i=k[t.pos];i>=0;i--){
			if(vis[t.pos+i]) break;
			vis[t.pos+i]=1;
			q.push({t.pos+i-a[t.pos+i],t.step+1}); //warn:回退a[t.pos+i] not [i]
		}
	}
	cout<<-1<<endl; //无法到达 
	
} 

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0; 
}