2416 参考答案

   1 /*
   2 zju 2416  BFS
   3 ymc 2008/5/21
   4 题目大意：
   5 数的转换，输入两个数，求第一个数转到第二个数的最快转换方法（最小步数）。
   6 转换规则：
   7 1，从1个数转到下一个数或前一个数，（1的前一个数是9，9的后一个数是1）
   8 2，相邻的数可以互相转换，最左边的数和最右边的数不相邻。
   9 进行一次转换算一步。
  10 
  11 */
  12 #include <iostream>
  13 #include <queue>
  14 using namespace std;
  15 const int N=10000;
  16 bool used[N];
  17 queue<int> a;
  18 queue<int> b;
  19 int tran[11]={9,1,2,3,4,5,6,7,8,9,1};
  20 int bit[4];
  21 void addtob(int u)
  22 {
  23         
  24         int next;
  25         int tmp=u;
  26         for(int i=3;i>=0;i--)
  27         {
  28                 bit[i]=tmp%10;
  29                 tmp=tmp/10;
  30         }
  31         for(int i=0;i<=3;i++)
  32         {
  33                 tmp=bit[i];
  34                 bit[i]=tran[bit[i]+1];
  35                 next=1000*bit[0]+100*bit[1]+10*bit[2]+bit[3];
  36                 if(!used[next]) { b.push(next);used[next]=true;}
  37                 bit[i]=tmp;
  38                 bit[i]=tran[bit[i]-1];
  39                 next=1000*bit[0]+100*bit[1]+10*bit[2]+bit[3];
  40                 if(!used[next]) { b.push(next);used[next]=true;}
  41                 bit[i]=tmp;
  42         }
  43         next=1000*bit[1]+100*bit[0]+10*bit[2]+bit[3];
  44         if(!used[next]) { b.push(next);used[next]=true;}
  45 
  46         next=1000*bit[0]+100*bit[2]+10*bit[1]+bit[3];
  47         if(!used[next]) { b.push(next);used[next]=true;}
  48 
  49         next=1000*bit[0]+100*bit[1]+10*bit[3]+bit[2];
  50         if(!used[next]) { b.push(next);used[next]=true;}
  51 }
  52 int BFS(int n,int m)
  53 {
  54         while(!a.empty())
  55                 a.pop();
  56         while(!b.empty())
  57                 b.pop();
  58         memset(used,0,sizeof(used));
  59         a.push(n);
  60         used[n]=true;
  61         int ans=0;
  62         int u;  
  63         while(1)
  64         {
  65                 while(!a.empty())
  66                 {
  67                         u=a.front();
  68                         if(u==m) return ans;
  69                         a.pop();
  70                         addtob(u);
  71                 }
  72                 while(!b.empty())
  73                 {
  74                         u=b.front();
  75                         b.pop();
  76                         a.push(u);
  77                 }
  78                 ans++;
  79         }
  80 }
  81 int main()
  82 {
  83         int test;
  84         cin>>test;
  85         int n,m;
  86         while(test-->0)
  87         {
  88                 cin>>n>>m;
  89                 cout<<BFS(n,m)<<endl;
  90         }
  91 }