60求助,大佬捞捞孩子
查看原帖
60求助,大佬捞捞孩子
1163062
whatsupman楼主2023/11/15 14:38
#include <stdio.h>
#include<math.h>
int m[300] = { 0 }, n, a, b, k1=0,flag=0;
int tree[10000000] = { 0 };
long long k2 = 0;
int main()
{
	int i, j;
	scanf("%d %d %d", &n, &a, &b);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &m[i + 1]);
	}
	tree[0] = a;
	if (a==b)
	{
		printf("0");
	}
	else
	{
		while (1)
		{
			long long k3 = k2;
			int flag1 = 0,flag2=0;
			k2 = k2+pow(2, k1);
			for ( i = k3; i < k2; i++)
			{
				if (tree[i]!=-1)
				{
					flag1 = 1;        /*出现一个可行点就会继续搜索下去*/
					tree[2 * i + 1] = tree[i] - m[tree[i]];
					tree[2 * i + 2] = tree[i] + m[tree[i]];
					if (tree[2 * i + 1] > n || tree[2 * i + 1] < 1)  /*-1表示该条分支不可行*/
					{
						tree[2 * i + 1] = -1;
					}
					else if (tree[2 * i + 1] == b)
					{
						flag2 = 1;
						break;
					}
					if (tree[2 * i + 2] > n || tree[2 * i + 2] < 1)
					{
						tree[2 * i + 2] = -1;
					}
					else if (tree[2 * i + 2] == b)  /*一旦找到第一个直接就是答案*/
					{
						flag2 = 1;
						break;
					}
				}
				else if (tree[i]==-1)        /*强行组成一个完全二叉树以方便后续判断*/
				{
					tree[2 * i + 1] = -1;
					tree[2 * i + 2] = -1;
				}
			}
			if (flag2==1)
			{
				break;
			}
			else
			{
				if (flag1==0)  /*如果flag=0说明没有可行点了,可跳出并输出-1*/
				{
					k1 = -2;
					break;
				}
				k1++;
			}
		}
		printf("%d", k1 + 1);
	}
}
2023/11/15 14:38
加载中...