#include<iostream>
using namespace std;
struct Position
{
	int cp;
	int minute;
};
int sp;//初始位置
int tp;//结束位置
int ans = 0xfffffff;//最少分钟数
Position Q[1000005];//队列
int vis[1000005] = { 0 };
int p1, p2;//队首，队尾指针
int In_q(int t)//判断当前位置是否入过队
{
	for (int i = p1; i < p2; i++)
		if (Q[i].cp == t)
			return 1;
	return 0;
}
void Rule_q(int r)//到达下一位置的方式
{
	switch (r)
	{
	case 3://当前位置-1
		Q[p2].cp = Q[p1].cp - 1;
		Q[p2].minute = Q[p1].minute + 1;
		break;
	case 2://当前位置+1
		Q[p2].cp = Q[p1].cp + 1;
		Q[p2].minute = Q[p1].minute + 1;
		break;
	case 1://当前位置*2
		Q[p2].cp = Q[p1].cp * 2;
		Q[p2].minute = Q[p1].minute + 1;
		break;
	}
}
int Check_q(int t)//剪枝
{
	if (t < sp / 2)//当前位置小于起点的一半
		return 0;
	if (t > tp/2*3 )//当前位置大于终点的1.5倍
		return 0;
	if (Q[p2].minute > ans)//达到当前位置花费的时间大于当前求得的最优解
		return 0;
		if (vis[t] == 1)//当前位置已经搜索过
			return 0;
	return 1;
}
int main()
{
	cin >> sp >> tp;
	if (sp >= tp)//人在牛的前面
		cout << sp - tp;
	else
	{
		p1 = 0, p2 = 1;
		Q[0].cp = sp;
		Q[0].minute = 0;//起点进队
		vis[Q[0].cp] = 1;
		while (p1 < p2&&p2<1000005)//队不空时
		{
			for (int r = 1; r <= 3; r++)//三种变换位置的方式
			{
				Rule_q(r);
				if (Q[p2].cp == tp)//找到终点
					if (Q[p2].minute < ans)
						ans = Q[p2].minute;
				if (Check_q(Q[p2].cp))//当前位置符合条件
				{
					vis[Q[p2].cp] = 1;
					p2++;//进队
				}
			}
			++p1;//出队
		}
		cout << ans;
	}
	return 0;
}

• Re:分支限界法 16ms（带注释） (1596) 201824100818 2019-12-24 21:05:58