Description
　　在一個(gè)裝滿財(cái)寶的屋子里，有2N個(gè)盒子排成一排。除了兩個(gè)相鄰的空盒外，其余的每個(gè)盒子里都裝有一個(gè)金球或者一個(gè)銀球，總共有N-1個(gè)金球和N-1個(gè)銀球。以下是一個(gè)N=5時(shí)的例子，G表示金球，S表示銀球：
　　
　　任意兩個(gè)相鄰的非空的盒子里的球可以移動(dòng)到兩個(gè)相鄰的空盒中，移動(dòng)不能改變這兩個(gè)球的排列順序。寫一個(gè)程序，用最少的移動(dòng)次數(shù)把所有的金球都移到所有銀球的左邊。

Input
　　輸入文件包含多組數(shù)據(jù)。第一行為K，表示數(shù)據(jù)的總數(shù)。
　　每組數(shù)據(jù)的第一行是N(3<=N<=7)，第二行是2N個(gè)盒子的初始狀態(tài)。金球用a表示，銀球用b表示，空盒用空格表示。每?jī)山M相鄰數(shù)據(jù)用空行隔開。

Output
　　對(duì)于每一組數(shù)據(jù)，若無解則輸出一行-1，若有解，輸出最少移動(dòng)次數(shù)，相鄰的兩組數(shù)據(jù)用一個(gè)空行隔開。

Sample Input
3
3
abab

5
abba abab

6
a babbababa

Sample Output
-1

3

4

Data Constraint
k<5
.
.
.
.
.

分析

可以直接用bfs來做，范圍小
對(duì)于普通的dfs，會(huì)死循環(huán)，考慮如何解決這個(gè)問題
我們想到對(duì)于一個(gè)格子只可能有三種情況：金、銀、空
那么我們可以用一個(gè)三進(jìn)制數(shù)來壓縮狀態(tài)
.
.
.
.
.

程序：

#include <iostream> #include <string.h> #include <stdio.h> using namespace std; int k,n,head,tail,x,p,f[1600000],a[16],b[16],w[100000][16]; char zf;bool check(int *x) {int y=0;for (int i=1;i<=n+1;i++){y+=x[i]&1;if (y==n-1) return 1;if (x[i]==2) return 0;} }void work(int *x) {int c=0; p=0;for (int i=1;i<=2*n;i++)if (x[i]==0&&c==0) c=1; else p=p*3+x[i]; }int bfs() {if (check(w[1])) return 0;head=0;tail=1;work(w[1]);f[p]=k;while (head<tail){head++;memcpy(a,w[head],sizeof(a)); memcpy(b,a,sizeof(b)); b[0]++;for (int i=1;i<=2*n-1;i++) if (a[i]==0) {x=i;break;}for (int i=1;i<=2*n-1;i++) if (a[i]!=0&&a[i+1]!=0){b[x]=a[i];b[x+1]=a[i+1];b[i]=b[i+1]=0; work(b);if (f[p]!=k){if (check(b)) return b[0];tail++;f[p]=k; memcpy(w[tail],b,sizeof(w[tail]));}b[i]=a[i];b[i+1]=a[i+1];}}return -1; }int main() {cin>>k;while (k>0){cin>>n;getchar(); for (int i=1;i<=2*n;i++){zf=getchar();w[1][i]=(zf==' '?0:zf-96);}cout<<bfs()<<endl;k--;} }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499922.html

總結(jié)

以上是生活随笔為你收集整理的【GDKOI2003】分球的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。