[搜索]ACM練習題：分球 ball 解題報告

題目來源：
1. 浙江理工大學 OnlineJudge 2584
2. 山東理工大學 OnlineJudge 1406

【問題描述】

在一個裝滿財寶的屋子裡，有2N個盒子排成一排。除了兩個相鄰的空盒外，其餘的每個盒子裡都裝有一個金球或者一個銀球，總共有N-1個金球和N-1個銀球。用圖6．3所示為一個N=5時的例子，G表示金球，S表示銀球。

G

S

S

G

G

S

G

S

任意兩個相鄰的非空的盒子裡的球可以移動到兩個相鄰的空盒中，移動不能改變這兩個球的排列順序。寫一個程序，用最少的移動次數把所有的金球都移到所有的銀球的左邊。

【輸入格式】

輸入文件包含多組資料。第一行為K，表示資料的總數。

每組資料的第一行是N(3≤N≤7)，

第二行是2N個盒子的初始狀態。金球用a表示， 銀球用b表示，空盒用空格表示。每兩組相鄰資料用空行隔開。

【輸出格式】

對於每一組資料，若無解則輸出一行NO SOLUTION，若有解，輸出一組狀態來表示移動的序列，每個狀態佔一行。每行輸出到此狀態的移動的步數，緊接著是一個空格，然後是此時的狀態。初始狀態為第0步，每組資料都要先輸出初始狀態。如有多種最少移動次數的方案，輸出“空格靠前靠左”的一種，如下兩種方案，需輸出第二種。

0 bbbb aaaa

1 bbbbaa aa

2 bbaabbaa

3 aabbaabb

4 aa aabbbb

0 bbbb aaaa

1 bbbbaaaa

2 aabbbb aa

3 aa bbbbaa

4 aaaabbbb

相鄰的兩組資料用一個空行隔開。

【輸入輸出樣例】

樣例輸入（balls.in）:

3

3

abab

5

abba abab

6

a babbababa

樣例輸出（balls.out）：

NO SOLUTION

0 abba abab

1 abbabaa b

2 a abaabbb

3 aaaab bbb

0 a babbababa

1 aabbabb aba

2 aabbabbbaa

3 aa abbbaabb

4 aaaaabbb bb

【分析】

簡單的廣度優先搜索～

（我現在才知道這種題目叫做『隱式圖』的廣度優先搜索）

由於暴力判重時間複雜度很大，所以可以使用哈希（Hash）判重。

由於每個格子只能有3種狀態，所以可以用『3進制數』來構造哈希。

因為3^14<5x10^6，不會開爆內存。

這道題困難的地方是空格的讀入，因為C++讀取文件中開頭的空格不能使用scanf("%c",&c)，也不能使用cin.get()，getline也不用，只能使用fstream的fin.get()。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25680

001 /*
002 *Problem: 分球
003 *Author: Yee-fan Zhu
004 *Website: www.yeefanblog.tk
005 */
006 #include <cstdio>
007 #include <cstring>
008 #include <cstdlib>
009 #include <fstream>
010 using namespace std;
011
012 ifstream fin("balls.in");
013 ofstream fout("balls.out");
014
015 typedef unsigned short int usint;
016
017 const int INF=100000000;
018 const int MAXN=16;
019 usint Ball[MAXN];
020 usint hash[5000001]={0};
021 int N;
022 int M;
023 int Head=0;
024 int Tail=0;
025
026 bool check(usint *str)
027 {
028     int s=0;
029     for(int i=1;i<=2*N;i++)
030     {
031         if(str[i]==2) break;
032         if(str[i]==1)
033             s++;
034     }
035     if(s==N-1)
036         return true;
037     return false;
038 }
039
040 void Print(usint *str)
041 {
042     int tmp;
043     for(int i=1;i<=2*N;i++)
044     {
045         tmp=str[i];
046         if(tmp==1) fout<<"a";
047         if(tmp==0) fout<<" ";
048         if(tmp==2) fout<<"b";
049     }
050     fout<<endl;
051 }
052
053 int Hash(usint *str)
054 {
055     int s=0;
056     int j=1;
057     for(int i=2*N;i>=1;i--)
058     {
059         if(str[i]==2)
060             s+=j;
061         else if(str[i]==0)
062             s+=2*j;
063         j*=3;
064     }
065     return s;
066 }
067
068 class QUEUE
069 {
070 public:
071     usint ball[16];
072     usint father;
073     usint pos;
074     usint step;
075     void clear()
076     {
077         for(int i=0;i<=15;i++)
078             ball[i]=0;
079     }
080 }; 
081 QUEUE Q[2000000];
082
083 usint Index[500000];
084 void Output(QUEUE x)
085 {
086    
087     usint top=0;
088     usint p=x.father;
089     while(p!=0)
090     {
091         top++;
092         Index[top]=p;
093         p=Q[p].father;
094     }
095     for(int i=top;i>=1;i--)
096     {
097         fout<<Q[Index[i]].step<<" ";
098         Print(Q[Index[i]].ball);
099     }
100     fout<<x.step<<" ";
101     Print(x.ball);
102 }
103
104 void Push(QUEUE x)
105 {
106     Tail++;
107     Q[Tail]=x;
108     hash[Hash(x.ball)]=1;
109 }
110
111 QUEUE Pop()
112 {
113     Head++;
114     return Q[Head];
115 }
116
117 void bfs()
118 {
119     QUEUE tmp,nxt;
120     tmp.clear();
121     for(int i=1;i<=2*N;i++)
122         tmp.ball[i]=Ball[i];
123     tmp.father=0;
124     tmp.step=0;
125     for(int i=1;i<=2*N;i++)
126     {
127         if(Ball[i]==0)
128         {
129             tmp.pos=i;
130             break;
131         }
132     }
133     Push(tmp);
134    
135     bool flag=true;
136    
137     usint tp;
138     while(Head!=Tail && flag)
139     {
140         tmp=Pop();
141         tp=tmp.pos;
142         for(int i=1;i<=2*N;i++)
143         {
144             if(tmp.ball[i]==0 || tmp.ball[i+1]==0)
145                 continue;
146             nxt=tmp;
147             nxt.father=Head;
148             nxt.pos=i;
149             nxt.ball[tp]=nxt.ball[i];
150             nxt.ball[tp+1]=nxt.ball[i+1];
151             nxt.ball[i]=0;
152             nxt.ball[i+1]=0;
153             nxt.step=tmp.step+1;
154             if(check(nxt.ball))
155             {
156                 Output(nxt);
157                 flag=false;
158                 return;
159             }
160             else
161                 if(hash[Hash(nxt.ball)]==0)
162                     Push(nxt);
163         }
164     }
165     fout<<"NO SOLUTION"<<endl;
166 }
167
168 void init()
169 {
170     fin>>M;
171     for(int i=1;i<=M;i++)
172     {
173         Head=0;
174         Tail=0;
175         fin>>N;
176         usint top=0;
177         char c;
178         while(top<2*N)
179         {
180             c=fin.get();
181             if(c!='a' && c!='b' && c!=' ')
182                 continue;
183             if(c=='a') Ball[++top]=1;
184             if(c=='b') Ball[++top]=2;
185             if(c==' ') Ball[++top]=0;
186         }
187         if(check(Ball))  {fout<<"0 ";Print(Ball);continue;}
188        
189         for(int i=0;i<=5000000;i++)
190             hash[i]=0;
191         bfs();
192         if(i<M)
193             fout<<endl;
194     }
195 }
196
197 int main()
198 {
199     init();
200     return 0;
201 }