POJ3278---Catch That Cow

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 100010;
int n, k;
bool vis[maxn];//存储是否访问过        只表示图中已经存在该点,后续不需要再次生成/访问.并不表示已经进行判断了.
int step[maxn];//存储走过步数
void solve()
{
  queue<int> Q;
  vis[n] = 1;
  step[n] = 0;
  Q.push(n);//起点入队
  while (!Q.empty())
  {
    int head = Q.front();
    Q.pop();
    if (head == k)
    {
      cout << step[head] << endl;
      return;
    }
    //访问其他可能的三个点.
    int x = head + 1;
    if (x <= 100000 && !vis[x])
    {
      step[x] = step[head] + 1;//步数+1
      vis[x] = true;
      Q.push(x);
    }
    x = head - 1;
    if (x >= 0 && !vis[x])
    {
      step[x] = step[head] + 1;
      vis[x] = true;
      Q.push(x);
    }
    x = head * 2;
    if (x <= 100000 && !vis[x])
    {
      step[x] = step[head] + 1;
      vis[x] = true;
      Q.push(x);
    }
  }
}
int main()
{
  while (cin >> n >> k)
  {
    if (n >= k)
    {
      cout << n - k << endl;
      continue;
    }
    memset(vis, false, sizeof(vis));//初始化数组
    memset(step, 0, sizeof(step));
    solve();
  }
  return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int dfs(int t)
{
  if(t<=n)
    if(n-t<t*2-n+1)
      return n-t;
    else
      return t*2-n+1;
  if(t%2==1)
    return min(min(dfs(t+1)+1,dfs(t-1)+1),t-n);
  else
    return min(dfs(t/2)+1,t-n);
}
int main()
{
  while(cin>>n>>m)
  {
    if(n>m)
    {
      cout<<n-m<<endl;
      continue;
    }
    int t=m;
    int ans=0;
    if(n==0)//这段很重要
    {
      n=1;
      ans=1;
    }
    ans+=dfs(t);
    cout<<ans<<endl;
  }
  return 0;
}