BFS 70分 MLE了,求助
查看原帖
BFS 70分 MLE了,求助
542893
tiaotiao0830楼主2023/5/14 10:42
#include<iostream>
#include<queue>
using namespace std;

int n,a,b,ans = 0x3f3f3f3f;
int lift[205];
int visited[205]; 
struct Node
{
	int floor;
	int steps;
};
Node tnode,pnode;
queue<Node> qlist;

void bfs(int a,int b,int n)
{
	tnode.floor = a;
	tnode.steps = 0;
	visited[a] = 1;
	qlist.push(tnode);
	
	while(!qlist.empty())
	{
		tnode = qlist.front();
		qlist.pop();
		
		if(tnode.floor == b)
		{
			ans = tnode.steps;
			break;
		}
		
		if(tnode.floor + lift[tnode.floor] <= n)
		{
			if(visited[tnode.floor + lift[tnode.floor]] == 0)
			{
				pnode.floor = tnode.floor + lift[tnode.floor];
				pnode.steps = tnode.steps + 1;
				qlist.push(pnode);
			}
		}
		
		if(tnode.floor - lift[tnode.floor] >= 1)
		{
			if(visited[tnode.floor - lift[tnode.floor]] == 0)
			{
				pnode.floor = tnode.floor - lift[tnode.floor];
				pnode.steps = tnode.steps + 1;
				qlist.push(pnode);
			}
		}
	}
}

int main()
{
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++)
	{
		cin >> lift[i];
	}                         //输入 
	
	bfs(a,b,n);                //BFS
	
	if(ans == 0x3f3f3f3f)
	{
		cout << -1 << endl;	 //ans没变,表示不可能 
	}
	else
	{
		cout << ans << endl; //输出ans 
	}
	return 0;
}

//1:前半句判断是否越界,后半句判断是否访问过 
2023/5/14 10:42
加载中...