3 条题解

  • 0
    @ 2024-4-6 15:52:08
    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <utility>
    #include <functional>
    
    using namespace std;
    
    int main() { 
    	int n, a, b;
    	scanf("%d %d %d", &n, &a, &b);
    	
    	vector<int> arr(n + 1);
    	for (int i = 1; i <= n; ++i)
    		scanf("%d", &arr[i]);
    	
    	long long res = 1e9;
    	vector<char> ita(n + 1, 0);
    // dfs 好像不行, 这样只有80分
    //	long long now = 0;
    //	function<void(int)> dfs = [&](int i) { // 递归爆炸 
    //		if (i <= 0 || i > n || ita[i])
    //			return;
    //		
    //		if (i == b) {
    //			res = min(res, now);
    //			return;
    //		}
    //		
    //		++now;
    //		ita[i] = 1;
    //		dfs(i + arr[i]);
    //		dfs(i - arr[i]);
    //		ita[i] = 0;
    //		--now;
    //	};
    	
    	queue<pair<int, long long>> Q; // 当前是第几层 , 操作次数 
    	Q.push({a, 0});
    	while (Q.size()) {
    		auto x = Q.front();
    		int cen = x.first;
    		long long cs = x.second;
    		Q.pop();
    		
    		if (cen == b) {
    			res = cs;
    			break;
    		}
    		
    		if (cen + arr[cen] <= n && !ita[cen + arr[cen]]) {
    			ita[cen + arr[cen]] = 1;
    			Q.push({cen + arr[cen], cs + 1});
    		}
    			
    		
    		if (cen - arr[cen] > 0 && !ita[cen - arr[cen]]) {
    			ita[cen - arr[cen]] = 1;
    			Q.push({cen - arr[cen], cs + 1});
    		}
    	}
    	
    //	dfs(a);
    	
    	printf("%lld\n", res == 1e9 ? -1 : res);
    	
    	return 0;
    }
    

    信息

    ID
    85
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    411
    已通过
    98
    上传者