为啥我并在一起循环就会mle,其中有个点tle,分开写就能ac?
mle,tle版:
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,a,b,arr[N],dis[N];
int d[]={1,-1};
void dfs(int x,int step)
{
dis[x]=step;
for(int i=0;i<2;++i)
{
int xx=x+d[i]*arr[x];
if(xx<1||xx>n||step>dis[xx]) continue;
dfs(xx,step+1);
}
}
int main()
{
memset(dis,0x3f,sizeof dis);
cin>>n>>a>>b;
for(int i=1;i<=n;i++) cin>>arr[i];
dfs(a,0);
cout<<((dis[b]==0x3f3f3f3f)?-1:dis[b])<<endl;
return 0;
}
正常ac版:
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,a,b,arr[N],dis[N];
int d[]={1,-1};
void dfs(int x,int step)
{
dis[x]=step;
int xx=x+arr[x];
if(xx>=1&&xx<=n&&step+1<dis[xx])
dfs(xx,step+1);
xx=x-arr[x];
if(xx>=1&&xx<=n&&step+1<dis[xx])
dfs(xx,step+1);
}
int main()
{
memset(dis,0x3f,sizeof dis);
cin>>n>>a>>b;
for(int i=1;i<=n;i++) cin>>arr[i];
dfs(a,0);
cout<<((dis[b]==0x3f3f3f3f)?-1:dis[b])<<endl;
return 0;
}