搜

暑假神（开学祭

2024-06-27 15:03:59

发布于：上海

29阅读

0回复

0点赞

暴搜即可。搜索树是无限深的，所以不可以深搜。广搜、迭搜（迭代加深搜索）和启搜（启发式搜索，A* 或 IDA*）都可以。广搜最好打，所以就选广搜啦。

时空复杂度： $O($ 能过 $)$ （逃

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct node{
	int x,cnt;
};

int a[205];
bool vis[205];

int main(){
	int n,A,b;
	cin >> n >> A >> b;
	for(int i=1; i<=n; i++) cin >> a[i];
	queue<node> q;
	q.push({A,0});
	while(!q.empty()){
		node f=q.front();
		vis[f.x]=1;
//		cout<<f.x<<" ";
		q.pop();
		if(f.x==b){
			cout << f.cnt;
			return 0;
		}
		if(f.x-a[f.x]>0&&!vis[f.x-a[f.x]]) q.push({f.x-a[f.x],f.cnt+1}),vis[f.x-a[f.x]]=1;
		if(f.x+a[f.x]<=n&&!vis[f.x+a[f.x]]) q.push({f.x+a[f.x],f.cnt+1}),vis[f.x+a[f.x]]=1;
	}
	cout<<-1;
	
	
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

复仇者_必胜啊ด้้（加团队

看，神搜可以过

#include<bits/stdc++.h>
using namespace std;
int n,A,B;
int ans=-1;
int a[205];
int vis[205];
clock_t st,ed;
bool check(int x){
	return x>=1 && x <= n;
}
void dfs(int x,int step){
	if(x == B){
        if(ans == -1)ans = step;
        else ans = min(ans,step);
        return;
	}
	if((double)(clock() - st)/CLOCKS_PER_SEC > 0.97)return;
   //if(ans!=-1 && step >= ans)return;
    int tmp = x+a[x];
    if(check(tmp) && !vis[tmp]){
        vis[tmp] = 1;
        dfs(tmp,step + 1);
        vis[tmp] = 0;
    }
    
    tmp = x-a[x];
    if(check(tmp) && !vis[tmp]){
        vis[tmp] = 1;
        dfs(tmp,step + 1);
        vis[tmp] = 0;
    }
    
    
}
int main(){
	st = clock();
    cin >> n >> A >> B;
    for(int i = 1 ; i <= n ;i++)cin >> a[i];
    vis[A] = 1;
    dfs(A,0);
    cout << ans << endl;
	return 0;
}

2024-11-30 来自广东