| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
双向BFS#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <bitset>
#define F "%I64d"
using namespace std;
typedef long long ll;
int dp[2][200000],N,K;
queue<int> QN,QK;
int bfs()
{
while(!QN.empty())QN.pop();
while(!QK.empty())QK.pop();
memset(dp,-1,sizeof dp);
QN.push(N);
QK.push(K);
dp[0][N] = dp[1][K] = 0;
while(1)
{
if(QN.front() > 1 && dp[0][QN.front() - 1] == -1)
{
dp[0][QN.front() - 1] = dp[0][QN.front()] + 1;
if(dp[1][QN.front() - 1] != -1)return dp[0][QN.front() - 1] + dp[1][QN.front() - 1];
QN.push(QN.front() - 1);
}
if(QN.front() < 100000 && dp[0][QN.front() + 1] == -1)
{
dp[0][QN.front() + 1] = dp[0][QN.front()] + 1;
if(dp[1][QN.front() + 1] != -1)return dp[0][QN.front() + 1] + dp[1][QN.front() + 1];
QN.push(QN.front() + 1);
}
if(QN.front() < 100000 && dp[0][QN.front() << 1] == -1)
{
dp[0][QN.front() << 1] = dp[0][QN.front()] + 1;
if(dp[1][QN.front() << 1] != -1)return dp[0][QN.front() << 1] + dp[1][QN.front() << 1];
QN.push(QN.front() << 1);
}
if(QK.front() > 1 && dp[1][QK.front() - 1] == -1)
{
dp[1][QK.front() - 1] = dp[1][QK.front()] + 1;
if(dp[0][QK.front() - 1] != -1)return dp[1][QK.front() - 1] + dp[0][QK.front() - 1];
QK.push(QK.front() - 1);
}
if(QK.front() < 100000 && dp[1][QK.front() + 1] == -1)
{
dp[1][QK.front() + 1] = dp[1][QK.front()] + 1;
if(dp[0][QK.front() + 1] != -1)return dp[1][QK.front() + 1] + dp[0][QK.front() + 1];
QK.push(QK.front() + 1);
}
if((QK.front() & 1) == 0 && dp[1][QK.front() >> 1] == -1)
{
dp[1][QK.front() >> 1] = dp[1][QK.front()] + 1;
if(dp[0][QK.front() >> 1] != -1)return dp[1][QK.front() >> 1] + dp[0][QK.front() >> 1];
QK.push(QK.front() >> 1);
}
QN.pop();
QK.pop();
}
}
int main()
{
N: while(~scanf("%d%d",&N,&K))
{
if(abs(N - K) <= 1){printf("%d\n",abs(N - K));continue;}
if((N << 1) == K){puts("1");continue;}
if(K < N){printf("%d\n",N - K);continue;}
printf("%d\n",bfs());
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator