100,TLE一个,求助
查看原帖
100,TLE一个,求助
875592
Rain_maple楼主2022/11/18 16:45
#include<iostream>
#include<cstdio>
#define min(x,y) x<y?x:y
using namespace std;
int num, sta, las;//分别为楼层,初始楼层和最终楼层
int sum=2000;//行动次数
int a[300] = { 0 };//各楼层能够行动的楼层数
bool b[1000];
void dfs(int x, int ans)
{
	if (x == las)
		sum = min(ans, sum);
	if (ans > sum)//剪枝
		return;
		b[x]=1;
	if (x + a[x] <= num&&b[x+a[x]]!=1)
	{
		dfs(x + a[x], ans+1);
	}
	if (x - a[x] >= 1 && b[x - a[x]] != 1)
	{ 
		dfs(x - a[x], ans+1);
	}
	b[x]=0;//回溯
}
int main()
{
	scanf("%d%d%d",&num,&sta,&las);
	for (int i = 1; i <= num; i++)
		scanf("%d",&a[i]);//各楼层行动数
	dfs(sta,0);
	if (sum == 2000)
		sum = -1;
	printf("%d",sum);
	return 0;
}
2022/11/18 16:45
加载中...