返回题解分享
讨论 / 题解分享/ 帖子详情

奇怪的电梯 - 题解

BFS



#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 210;
int n, a, b;
int arr[N], d[N];
int m[2] = {1, -1};
queue<int> q;

int bfs(int a, int b) // a, b 为下标(电梯楼层)
{
	q.push(a);
	
	d[a] = 0;
	
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		
		for (int i = 0; i <= 1; i++)
		{
			int nx = t + arr[t] * m[i];
			
			if (nx >= 1 && nx <= n && d[nx] == -1)
			{
				d[nx] = d[t] + 1;
				q.push(nx);
			}
		}
	}
	return d[b];
}

int main()
{
	cin >> n >> a >> b;
	
	for (int i = 1; i <= n; i++) cin >> arr[i];
	
	memset(d, -1, sizeof d);
	
	cout << bfs(a, b);
	
	return 0;
}
0 回复 0 转发 0 喜欢 7 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!