都是深搜 为什么分数不一样
查看原帖
都是深搜 为什么分数不一样
974277
水星湖psgqwq楼主2023/8/25 19:37

我的:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int minn=2e9,n,a,b,k[205],box[205];//box表示每层楼出现的次数,为2停止,要回溯!! 
void dfs(int step,int nowf)
{
	if(nowf==b)
	{
		minn = min(minn,step-1);
		return;
	}
	if(box[nowf]==2)return;
	if(nowf+k[nowf]<=n)
	{
		box[nowf+k[nowf]]++;
		dfs(step+1,nowf+k[nowf]);
		box[nowf+k[nowf]]--;
	}
	if(nowf-k[nowf]>=1)
	{
		box[nowf-k[nowf]]++;
		dfs(step+1,nowf-k[nowf]);
		box[nowf-k[nowf]]--;
	}

}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) 
		cin>>k[i];
	dfs(1,a);
	if(minn == 2e9)cout<<-1;
	else
		cout<<minn;
	return 0;
}

(80pts)

题解的:

#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,ans=0x7ffffff;
int to[205];
bool vis[205];
void dfs(int now,int sum)//now表示当前搜到的楼层,sum表示按钮次数
{
    if(now==b) ans=min(ans,sum);
    if(sum>ans) return;
    vis[now]=1;
    //不越界就搜
    if(now+to[now]<=n&&!vis[now+to[now]]) dfs(now+to[now],sum+1);
    if(now-to[now]>=1&&!vis[now-to[now]]) dfs(now-to[now],sum+1);
    vis[now]=0;//回溯
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++) scanf("%d",&to[i]);
    vis[a]=1;
    dfs(a,0);
    if(ans!=0x7ffffff) printf("%d",ans);
    else printf("-1");
    return 0;
}

(100pts unaccept) 两种都卡第一个点了

2023/8/25 19:37
加载中...