回家的路(BFS)

 题目描述

直线上依次有 1～n 号位置，相邻位置距离为 1，部分位置上有百合花，只有这些位置青蛙可以站上去。一只青蛙在 1 号位置，而它的家在 n 号位置，他每次可以跳两步或者三步。你要计算青蛙至少跳几次可以到家。

【输入格式】

输入共 2 行:
第 1 行，一个整数 n，意义如题目描述；
第 2 行，n 长度的由 0,1 组成的字符串，依次表示 1～n 号位置是否有百合花，1表示有，0表示无。

【输出格式】

输出共 1 行:
第 1 行，1 个整数，为青蛙到家至少需要跳的次数，如果它不可能回家则输出 -1。

#include <iostream>
#include <queue>
using namespace std;

bool vis[105], a[105];
int n, dis[105];

int bfs()
{
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int x = q.front();
		if (x == n)
		{
			return dis[x];
		}
		q.pop();
		int y = x + 3;
		if (y <= n && !vis[y] && a[y])
		{
			q.push(y);
			vis[y] = 1;
			dis[y] = dis[x] + 1;
		}
		y = x + 2;
		if (y <= n && !vis[y] && a[y])
		{
			q.push(y);
			vis[y] = 1;
			dis[y] = dis[x] + 1;
		}
	}
	return -1;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	cout << bfs() << endl;
	return 0;
}