80 #9#10WA 已经剪枝 感谢相助
查看原帖
80 #9#10WA 已经剪枝 感谢相助
803133
CYF123469楼主2023/3/19 12:14
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std ;
const int maxn=210 ;
int N,A,B ;
int mp[maxn] ;
int vis[maxn] ;
struct node 
{
	int st,step ;
};
void bfs()
{
	if(A==B) 
	{
		printf("0\n") ;
		return ;
	}
	queue<node>q ;
	q.push({A,0}) ;
	while(!q.empty())
	{
		node t ;
		t=q.front() ;
		q.pop() ;
		if(t.st==B)  
		{
			printf("%d\n",t.step+1) ;
			return ;
		}
		else 
		{
			if(t.st+mp[t.st]>=1&&t.st+mp[t.st]<=N&&!vis[t.st+mp[t.st]])
			{
				if(t.st+mp[t.st]==B) 
				{
					printf("%d\n",t.step+1) ;
					return ;
				}
				else 
				{
					vis[t.st+mp[t.st]]=1 ;
					q.push({t.st+mp[t.st],t.step+1}) ;	
				}
			}
			else if(t.st-mp[t.st]>=1&&t.st-mp[t.st]<=N&&!vis[t.st-mp[t.st]])
			{
				if(t.st-mp[t.st]==B) 
				{
					printf("%d\n",t.step+1) ;
					return ;
				}
				else 
				{
					vis[t.st-mp[t.st]]=1 ;
					q.push({t.st-mp[t.st],t.step+1}) ;	
				}
			}
		}
	} 
	printf("-1\n") ;
}
int main()
{
	scanf("%d %d %d",&N,&A,&B) ;
	memset(mp,0,sizeof(mp)) ;
	memset(vis,0,sizeof(vis)) ;
	for(int i=1;i<=N;i++) cin>>mp[i] ;
	bfs() ;
	return 0 ;
}
2023/3/19 12:14
加载中...