POJ 1184-Start typist
50986 ワード
転載は出所を明記してください。優YoU http://user.qzone.qq.com/289065406/blog/1311864665
大体の意味：
l 与えられた6つの操作で6桁を別の6桁に変えて、必要な最低操作数を求めます。
l 6つの操作:
l 左に移動します。カーソル位置を1桁左または右に移動します。1番目の位置では左に移動できません。最後のビットでは右に移動できません。
l 左と右の交換：カーソル位置の数字を最初または最後のビットと交換します。
l カーソル位置の数字を大きくまたは小さくします。
問題解決の考え方：
BFS+状態圧縮
初歩的な考え
l 有効な欲張りアルゴリズムは見つけにくいです。
l 明らかな局所最適特性がなくて、動態的に計画することができません。
l 検索を考慮する
直観的な考え
l 直接検索を行い、初期状態から最後の状態の最適解が見つかるまで分かります。
l 空間でも時間でも通じない。
l 6つの位置×100000個の異なる数＝600万個の状態
l 状態数を減らす必要があります。
二つの操作の分離
l この6つの操作は一つの数に二つの影響を与え、一つは二つの桁の位置を交換すること、もう一つはある桁の値を変えることです。
l カーソルがある数桁に到達する場合にのみ、この数桁の値の変化が発生し、その発生時間は重要ではない。
l したがって、すべての動作は、シフトおよび交換動作、一つは増大および縮小動作の2つに分けることができる。
l 操作を分離します。まず、元の数の各桁を並べ直します。（シフトと交換操作を利用して）、カーソルが到達した位置を大きくします。
問題転化：
l 1.各配列とカーソルの到達状況に対して、必要最小限の操作数を求める。（このプロセスは入力に関係なく）
l 2.各配列の下で、必要な操作の増大と減少の回数を求める。（変更が必要なすべてのビットがアクセスされました）
問題を解く第一歩
l 状態の数:
l 6つの位置×720種類の配置状況×26種類のカーソルアクセス状況
l さらに縮小した状態の数:
l カーソルは連続して移動しますので、6位以外のいずれかが訪問された場合は、その前の数桁が訪問されます。6位右の交換操作でアクセスできます。この列ではありません。
l これにより10種類のカーソルアクセスが得られます。
l 1訪問されました
l 1,2訪問されました
l 1,2,3が訪問されました
l 1,2,3,4が訪問されました。
l 1,2,3,4,5が訪問されました。
l 1,6が訪問されました
l 1,2,6が訪問されました
l 1,2,3,6が訪問されました。
l 1,2,3,4,6が訪問されました。
l 1,2,3,4,5,6が訪問されました。
l 現在の状態数は6です×720×10,受けられます
l 検索方法:
l 左にシフトし、右にシフトし、左に交換し、右に4つの操作を交換して検索します。左に移動する操作は無駄な操作であることが分かりにくいです。数字の大きさを変えてから右に移動したり交換したりできます。
l 検索深さを予知できません。最適解は浅い層で得られますので、広さ優先アルゴリズムを採用します。
問題を解く第二歩
l 要求を満たすすべての場合（つまり、大きさを変える必要がある数桁のカーソルがすべて訪れたことがあります）には、総操作が最も少ないものを探して出力します。
大体の意味：
l 与えられた6つの操作で6桁を別の6桁に変えて、必要な最低操作数を求めます。
l 6つの操作:
l 左に移動します。カーソル位置を1桁左または右に移動します。1番目の位置では左に移動できません。最後のビットでは右に移動できません。
l 左と右の交換：カーソル位置の数字を最初または最後のビットと交換します。
l カーソル位置の数字を大きくまたは小さくします。
問題解決の考え方：
BFS+状態圧縮
初歩的な考え
l 有効な欲張りアルゴリズムは見つけにくいです。
l 明らかな局所最適特性がなくて、動態的に計画することができません。
l 検索を考慮する
直観的な考え
l 直接検索を行い、初期状態から最後の状態の最適解が見つかるまで分かります。
l 空間でも時間でも通じない。
l 6つの位置×100000個の異なる数＝600万個の状態
l 状態数を減らす必要があります。
二つの操作の分離
l この6つの操作は一つの数に二つの影響を与え、一つは二つの桁の位置を交換すること、もう一つはある桁の値を変えることです。
l カーソルがある数桁に到達する場合にのみ、この数桁の値の変化が発生し、その発生時間は重要ではない。
l したがって、すべての動作は、シフトおよび交換動作、一つは増大および縮小動作の2つに分けることができる。
l 操作を分離します。まず、元の数の各桁を並べ直します。（シフトと交換操作を利用して）、カーソルが到達した位置を大きくします。
問題転化：
l 1.各配列とカーソルの到達状況に対して、必要最小限の操作数を求める。（このプロセスは入力に関係なく）
l 2.各配列の下で、必要な操作の増大と減少の回数を求める。（変更が必要なすべてのビットがアクセスされました）
問題を解く第一歩
l 状態の数:
l 6つの位置×720種類の配置状況×26種類のカーソルアクセス状況
l さらに縮小した状態の数:
l カーソルは連続して移動しますので、6位以外のいずれかが訪問された場合は、その前の数桁が訪問されます。6位右の交換操作でアクセスできます。この列ではありません。
l これにより10種類のカーソルアクセスが得られます。
l 1訪問されました
l 1,2訪問されました
l 1,2,3が訪問されました
l 1,2,3,4が訪問されました。
l 1,2,3,4,5が訪問されました。
l 1,6が訪問されました
l 1,2,6が訪問されました
l 1,2,3,6が訪問されました。
l 1,2,3,4,6が訪問されました。
l 1,2,3,4,5,6が訪問されました。
l 現在の状態数は6です×720×10,受けられます
l 検索方法:
l 左にシフトし、右にシフトし、左に交換し、右に4つの操作を交換して検索します。左に移動する操作は無駄な操作であることが分かりにくいです。数字の大きさを変えてから右に移動したり交換したりできます。
l 検索深さを予知できません。最適解は浅い層で得られますので、広さ優先アルゴリズムを採用します。
問題を解く第二歩
l 要求を満たすすべての場合（つまり、大きさを変える必要がある数桁のカーソルがすべて訪れたことがあります）には、総操作が最も少ないものを探して出力します。
1 //Memory Time
2 //3000K 0MS
3
4 #include<iostream>
5 #include<queue>
6 #include<cmath>
7 using namespace std;
8
9 class oper // ( ， )，
10 {
11 public:
12 int num[6]; // step " "
13 int state; // step " " , VistState ， 0~9
14 int pos; // step " " ， 0~5
15 int step; // " "
16 };
17
18 int VistState[10][6]= /* ， swap0、swap1 " "*/
19 { /* ，1 ，0 */
20
21 1,0,0,0,0,0, /* 0: (pos=0)*/
22 1,1,0,0,0,0, /* 1: 0 (pos=1)， 1 swap0 (pos=1)*/
23 1,1,1,0,0,0, /* 2: 1 (pos=2)， 2 swap0 (pos=2)*/
24 1,1,1,1,0,0, /* 3: 2 (pos=3)， 3 swap0 (pos=3)*/
25 1,1,1,1,1,0, /* 4: 3 (pos=4)， 4 swap0 (pos=4)*/
26 1,0,0,0,0,1, /* 5: 0 swap1 (pos=0)， 5 swap0 (pos=0)*/
27 1,1,0,0,0,1, /* 6: 1 swap1 (pos=1)， 5 (pos=1), 6 swap0 (pos=1)*/
28 1,1,1,0,0,1, /* 7: 2 swap1 (pos=2)， 6 (pos=2), 7 swap0 (pos=2)*/
29 1,1,1,1,0,1, /* 8: 3 swap1 (pos=3)， 7 (pos=3), 8 swap0 (pos=3)*/
30 1,1,1,1,1,1 /* 9: 4 swap1 (pos=4)， 8 (pos=4), 9 (pos=5),
31 4 (pos=5)， 9 swap0 ， 9 swap1 */
32 };
33 /* :swap0 , pos , ; swap0 ,pos ;
34 ,pos+1 ; */
35
36 int comb[720][8]; // num ( ， )， 6!=720
37 //comb[][0~5]=num[0~5], comb[][6]=state , comb[][7]=step
38 int idx=0; //comb
39 bool vist[6][6][6][6][6][6][6][10]; // ， 6 num[]， 7 pos， 8 state
40
41 void BFS(void); // " "
42 bool CheckVist(oper* a); //
43 void ChangeVist(oper* a); //
44
45 int main(void)
46 {
47 memset(vist,false,sizeof(vist));
48 BFS(); // : ， " "。( )
49
50 char Init_ANum[6]; //
51 int Init_DNum[6]; //
52 char Aim_ANum[6]; //
53 int Aim_DNum[6]; //
54
55 while(cin>>Init_ANum>>Aim_ANum)
56 {
57 for(int k=0;k<6;k++) //
58 {
59 Init_DNum[k]=Init_ANum[k]-'0';
60 Aim_DNum[k]=Aim_ANum[k]-'0';
61 }
62
63 int MinOper=1000000; // str aim
64 for(int i=0;i<idx;i++)
65 {
66 int cnt=comb[i][7]; //comb[i][7]=step,
67 bool flag=true;
68 for(int j=0;j<6;j++)
69 { //comb[i][6]=state
70 if(!VistState[ comb[i][6] ][j] && (Init_DNum[ comb[i][j] ]!=Aim_DNum[j])) //str[] aim[] j ，
71 {
72 flag=false; //comb[i]
73 break;
74 }
75 else
76 cnt+=abs(Init_DNum[ comb[i][j] ] - Aim_DNum[j]); // ， ( 1)
77 }
78
79 if(flag)
80 MinOper=MinOper<cnt?MinOper:cnt;
81 }
82
83 cout<<MinOper<<endl;
84 }
85
86 return 0;
87 }
88
89 /* " " */
90 void BFS(void)
91 {
92 oper a,b;
93 queue<oper>Q;
94
95 for(int i=0;i<6;i++)
96 a.num[i]=i;
97 a.pos=a.state=a.step=0;
98
99 Q.push(a); //
100 ChangeVist(&a);
101
102 while(!Q.empty())
103 {
104 a=Q.front(); //
105 Q.pop(); //
106
107 /* */
108
109 for(int k=0;k<6;k++)
110 comb[idx][k]=a.num[k];
111 comb[idx][6]=a.state;
112 comb[idx++][7]=a.step;
113
114 if(a.pos>0) //swap0 ， swap0 ，
115 { // b.state b.pos
116
117 /*swap0 */
118
119 b=a; //
120 b.step=a.step+1;
121 swap(b.num[0],b.num[b.pos]); // num 0 pos
122 if(!CheckVist(&b)) //
123 {
124 ChangeVist(&b);
125 Q.push(b); //
126 }
127 }
128
129 if(a.pos<5) // right swap1
130 {
131 /*right ， pos */
132
133 b=a;
134 b.step=a.step+1;
135 b.pos++;
136 if(b.state<9)
137 b.state++;
138
139 if(!CheckVist(&b)) //
140 {
141 ChangeVist(&b);
142 Q.push(b); //
143 }
144
145 /*swap1 , pos */
146
147 b=a;
148 b.step=a.step+1;
149 swap(b.num[5],b.num[b.pos]); // num 5 pos
150 if(b.state<5)
151 b.state+=5;
152
153 if(!CheckVist(&b)) //
154 {
155 ChangeVist(&b);
156 Q.push(b); //
157 }
158 }
159 }
160 return;
161 }
162
163 /* */
164 bool CheckVist(oper* a)
165 {
166 int* p=a->num;
167 return vist[*p][*(p+1)][*(p+2)][*(p+3)][*(p+4)][*(p+5)][a->pos][a->state];
168 }
169
170 /* */
171 void ChangeVist(oper* a)
172 {
173 int* p=a->num;
174 vist[*p][*(p+1)][*(p+2)][*(p+3)][*(p+4)][*(p+5)][a->pos][a->state]=true;
175 return;
176 }