|
⇤ ← 于2008-11-12 14:10:02修订的的版本1
大小: 1853
备注:
|
← 于2008-11-12 14:10:52修订的的版本2 ⇥
大小: 4199
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 95: | 行号 95: |
| {{{ #!cplusplus /* zju 2416 BFS ymc 2008/5/21 题目大意： 数的转换，输入两个数，求第一个数转到第二个数的最快转换方法（最小步数）。 转换规则： 1，从1个数转到下一个数或前一个数，（1的前一个数是9，9的后一个数是1） 2，相邻的数可以互相转换，最左边的数和最右边的数不相邻。 进行一次转换算一步。 分析与解题思路： */ #include <iostream> #include <queue> using namespace std; const int N=10000; bool used[N]; queue<int> a; queue<int> b; void addtob(int u) { int t,x,y,z; int next; int tmp=u; z=tmp%10;tmp=tmp/10; y=tmp%10;tmp=tmp/10; x=tmp%10; t=tmp/10; if(t==9) next=u-8000;//第1位加1 else next=u+1000; if(!used[next]) { b.push(next);used[next]=true;} if(x==9) next=u-800; //第2位加1 else next=u+100; if(!used[next]) { b.push(next);used[next]=true;} if(y==9) next=u-80; //第3位加1 else next=u+10; if(!used[next]) { b.push(next);used[next]=true;} if(z==9) next=u-8; //第4位加1 else next=u+1; if(!used[next]) { b.push(next);used[next]=true;} if(t==1) next=u+8000;//第1位减1 else next=u-1000; if(!used[next]) { b.push(next);used[next]=true;} if(x==1) next=u+800; //第2位减1 else next=u-100; if(!used[next]) { b.push(next);used[next]=true;} if(y==1) next=u+80; //第3位减1 else next=u-10; if(!used[next]) { b.push(next);used[next]=true;} if(z==1) next=u+8; //第4位减1 else next=u-1; if(!used[next]) { b.push(next);used[next]=true;} next=x*1000+t*100+10*y+z; //1,2 if(!used[next]) { b.push(next);used[next]=true;} next=1000*t+y*100+x*10+z; //2,3 if(!used[next]) { b.push(next);used[next]=true;} next=1000*t+x*100+z*10+y; //3,4 if(!used[next]) { b.push(next);used[next]=true;} } int BFS(int n,int m) { while(!a.empty()) a.pop(); while(!b.empty()) b.pop(); memset(used,0,sizeof(used)); a.push(n); used[n]=true; int ans=0; int u; while(1) { while(!a.empty()) { u=a.front(); if(u==m) return ans; a.pop(); addtob(u); } while(!b.empty()) { u=b.front(); b.pop(); a.push(u); } ans++; } } int main() { int test; cin>>test; int n,m; while(test-->0) { cin>>n>>m; cout<<BFS(n,m)<<endl; } } }}} |
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 }