View Code of Problem 1030

#include<cstdio>
#include<iostream>
#define MAXN 800000
using namespace std;
struct T
{
	int num1,num2,step;
}q[MAXN];
bool vis[20500][105];
int n;
int head,tail;
bool add(int num1,int num2,int step)//其实就是一个BFS，维护num1 > num2
{
	if(num1 == n||num2 == n)//达到目标状态
	{
		return true;
	}
	if(num1 < num2)
		swap(num1,num2);
		if(num1 == num2||num1 >= n + 101|| num2 >= 101)//两个数相等，则无最优解；第一个数超过n太多无解；第二个数太大会运行错误
		return false;
	if(!vis[num1][num2])//入队列
	{
		vis[num1][num2] = 1;
		tail++;
		q[tail].num1 = num1;
		q[tail].num2 = num2;
		q[tail].step = step;
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	head = tail = -1;
	add(1,0,0);//初始状态的两个数,num1 = 1,num2 = 0
	int num1,num2,step;
	int ans;
	while(head < tail)
	{
		++head;
		num1 = q[head].num1,num2 = q[head].num2,step = q[head].step + 1;
		if(add(num1+num1,num2,step) || add(num1,num2+num2,step) || add(num1,num1+num2,step) || add(num2,num1+num2,step) || add(num1,num1+num1,step) || add(num2,num2+num2,step) || add(num1 - num2,num2,step) || add(num1,num1 - num2,step))//考虑所有保和运算的情况，全部入队
		{
			ans = step;
			break;
		}
	}
	printf("%d\n",ans);
}