首页 > 代码库 > 种花小游戏 随机化搜索

种花小游戏 随机化搜索

植物大战僵尸这款游戏中,还有个特别有意思的赚钱方式——种花(能长金币的花)。
种出来的金币需要玩家点击才能得到,或者,玩家可以购买一只蜗牛来帮助捡金币。然而,蜗牛爬得慢是众所周知的。所以,场上有若干金币时,蜗牛总是喜欢以最少的行程来捡走所有的金币。
现在告诉你场上n个金币所在位置的坐标,以及蜗牛所在位置,让你求出蜗牛捡走所有金币的最小行程。

 

比较神奇,数据量是16,dfs可以过;随机化搜索,很稳定(所有的点都相同的时间);

 

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<ctime> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 #define up(i,p,n) for(int i=p;i<=n;i++) 8 #define down(i,n,p) for(int i=n;i>=p;i--) 9 namespace OI{10     const int maxn=20,inf=100000000;11     int n,a[maxn][2],q[maxn];12     double d[maxn][maxn];13     void swa(int i,int j){14         for(;i<=j;i++,j--){15             swap(q[i],q[j]);16         }17     }18     double slove(){19         up(i,1,100){20             int x=rand()%n+1;21             int y=rand()%n+1;22             if(x==n)x=n-1;if(y==n)y=n-1;23             swap(q[x],q[y]);24         }25         up(i,1,n)up(j,i+1,n-1)26         if(d[q[i]][q[i+1]]+d[q[j-1]][q[j]]>d[q[i]][q[j-1]]+d[q[i+1]][q[j]])swa(i+1,j-1);27         double t=0;28         up(i,1,n-1)t+=d[q[i]][q[i+1]];29         return t;30     }31     int squ(int x){return x*x;}32     void init(){33         srand(time(0));34         scanf("%d",&n);n++;35         up(i,1,n)scanf("%d%d",&a[i][0],&a[i][1]);36         up(i,1,n)up(j,1,n)37                 d[i][j]=sqrt(1.0*squ(a[i][0]-a[j][0])+squ(a[j][1]-a[i][1]));38         //up(i,1,n)up(j,1,n)printf("%d %d %.2lf\n",i,j,d[i][j]);39         up(i,1,n)q[i]=i;40         double ans=(double)inf;41         up(i,1,50000){42             double t=slove();43             if(t<ans)ans=t;44         }45         printf("%.2lf\n",ans);46     }47 }48 int main(){49     //freopen("1.in","r",stdin);50     //freopen("1.out","w",stdout);51     OI::init();52     return 0;53 }
View Code

 

种花小游戏 随机化搜索