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 }

   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 */
  13 #include <iostream>
  14 #include <queue>
  15 using namespace std;
  16 const int N=10000;
  17 bool used[N];
  18 queue<int> a;
  19 queue<int> b;
  20 void addtob(int u)
  21 {
  22         int t,x,y,z;
  23         int next;
  24         int tmp=u;
  25         z=tmp%10;tmp=tmp/10;
  26         y=tmp%10;tmp=tmp/10;
  27         x=tmp%10;
  28         t=tmp/10;
  29 
  30 
  31         if(t==9) next=u-8000;//第1位加1
  32         else next=u+1000;
  33         if(!used[next]) { b.push(next);used[next]=true;}
  34 
  35         if(x==9) next=u-800;  //第2位加1
  36         else    next=u+100;
  37         if(!used[next]) { b.push(next);used[next]=true;}
  38 
  39         if(y==9) next=u-80;  //第3位加1
  40         else    next=u+10;
  41         if(!used[next]) { b.push(next);used[next]=true;}
  42 
  43         if(z==9)  next=u-8; //第4位加1
  44         else    next=u+1;
  45         if(!used[next]) { b.push(next);used[next]=true;}
  46 
  47         if(t==1) next=u+8000;//第1位减1
  48         else next=u-1000;
  49         if(!used[next]) { b.push(next);used[next]=true;}
  50 
  51         if(x==1) next=u+800;  //第2位减1
  52         else    next=u-100;
  53         if(!used[next]) { b.push(next);used[next]=true;}
  54 
  55         if(y==1) next=u+80;  //第3位减1
  56         else    next=u-10;
  57         if(!used[next]) { b.push(next);used[next]=true;}
  58 
  59         if(z==1)  next=u+8;  //第4位减1
  60         else    next=u-1;
  61         if(!used[next]) { b.push(next);used[next]=true;}
  62 
  63         next=x*1000+t*100+10*y+z;  //1,2
  64         if(!used[next]) { b.push(next);used[next]=true;}
  65 
  66         next=1000*t+y*100+x*10+z; //2,3
  67         if(!used[next]) { b.push(next);used[next]=true;}
  68 
  69         next=1000*t+x*100+z*10+y; //3,4
  70         if(!used[next]) { b.push(next);used[next]=true;}
  71 
  72 }
  73 int BFS(int n,int m)
  74 {
  75         while(!a.empty())
  76                 a.pop();
  77         while(!b.empty())
  78                 b.pop();
  79         memset(used,0,sizeof(used));
  80         a.push(n);
  81         used[n]=true;
  82         int ans=0;
  83         int u;
  84         while(1)
  85         {
  86                 while(!a.empty())
  87                 {
  88                         u=a.front();
  89                         if(u==m) return ans;
  90                         a.pop();
  91                         addtob(u);
  92                 }
  93                 while(!b.empty())
  94                 {
  95                         u=b.front();
  96                         b.pop();
  97                         a.push(u);
  98                 }
  99                 ans++;
 100         }
 101 }
 102 int main()
 103 {
 104         int test;
 105         cin>>test;
 106         int n,m;
 107         while(test-->0)
 108         {
 109                 cin>>n>>m;
 110                 cout<<BFS(n,m)<<endl;
 111         }
 112 }