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