Hopping dots (独立钻石棋变种)攻略

版权摊牌:定冠词是视频博客作者的原始的文字。,故障博主批准,不得反复无常地转载。。

引进:定冠词,我以为议论一任一某一完全的游玩。,呼叫跳频 dots,翻译成逻辑困难。

关键词:独立钻石棋、吃水占先搜索、可能性辨析、遗产紧缩、静态放映记载方式

一,下载节

点击翻开节(因互联网网络) 或许点击翻开的节(因我的百度云)

我的版本:Hopping dots 1.1

二,游玩接合、西洋跳棋盘、国际象棋的棋子

(下面是第一个人)

西洋跳棋盘是由13点结合的。


国际象棋的棋子:1颗白色的种子和若干绿色的种子。

三,整齐的

鉴于独立钻石棋的整齐的停止吃子,只剩一任一某一孩子了。,为了红小伙子,那就是赢。轻视白色在哪里。

这是我本人的整齐的。,非常赞许地精炼,开端时注意是翻转的。,慎熟虑性质上和法定的限界相似的。。

四,初步看法

1,国际象棋的棋子的总共

至多有12件。,无论健康状况如何有1个。。

这13片必然是死了。,因心不在焉办法买卖。。

12卒状态,心不在焉生活环境。,这是暂定的未知的。。

2,国际象棋的棋子数的换衣

每个买卖,件数少于1件。,因而,无论哪些情境,至多正是11个手术。

3,成绩理想化

成绩理想化版:正是绿色的小伙子心不在焉白色的增加。,是否只剩一任一某一孩子了。那就是赢(同一无论得第二名)

这样的事物的版本就更在附近独立钻石棋了,精确,更西洋跳棋盘和独立钻石棋不相似的在远处,心不在焉区别。。

为球员,原成绩和成绩理想化版多样性并故障很大,这实际上是很难玩的。。

四处走动的那些的需求的东西做实际辨析的人,,成功实现的事的成绩辨析起来很复杂。,毯子很多的法度。

是否你只想整齐的写吃水占先搜索顺序到S,心不在焉必要停止理想化。,不管怎样是否你想从事更顽固的。,率先,从实际上辨析了可能性浆糊。,因而理想化是要做的第一步。。

4,情境的总共(成绩理想化版)

有13点可能会有孩子。,因而状态的总共是2 ^ 13=8192。

它也包罗很多绝境。,有本利之和具体状态?,咱们不重要的。。

5,编号


6,记载主宰边(不思索轴承)

不难计数,有16个领域。

以2、6、8、12四处走动的中部的的每一侧,有1个。,如1-2-3

以4、5、9、10个中部的有2个边。,如1-4-7,2-4-6

以7为当中点,有4个领域。,如2-7—12,4-7-10

不思索轴承,因无论哪些时期。,一面对应于一任一某一可塑的的买卖。,

以边1-2-3为例,在同一的状态下,从1到3和从3到1都是不克不及整个买卖的。。

注意到,每边的3个数字是相当的衣服。,因而支持只需求记载2位数字。,

这样的事物,你可以应用2个16个规模的衣服来记载16个边。。

int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};

五,吃水占先搜索的可能性辨析(成绩理想化版)

因至多正是11个手术。,因而吃水占先搜索故障很深。。如今需求计算的是,每个买卖有本利之和种选择?

1,在无论哪些状态下有本利之和选择?

咱们需求一任一某一应变量。,出口一任一某一情境,出口数值,通知咱们咱们有本利之和选择。。

健康状况如何出口?应用遗产紧缩是最适当的的。。

13点,每个点对应于一任一某一一块。,1残忍的孩子。,0残忍的心不在焉孩子。,这样的事物,8192个情境便可以和8192个13位二元系数一一对应了。

出口后来,该应变量可以整齐的计算选择的总共。,时期是O(1)。

用左右应变量,只从0到8191数n。,你可以找出f(n)的最大量的。,成功实现的事10

行为准则:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};intf(int n){int r =0, s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}return r;}intmain(){int maxx =0;for(int n =0; n <8192; n++)if(maxx <f(n))maxx =f(n);
	cout << maxx;return0;}

2,吃水占先搜索的不均一

找出后面。,一任一某一状态至多可以运转11次在上文中。,每个买卖至多10种选择,这么,用吃水占先搜索处理左右成绩至多需求10^11次数计算。这是一任一某一非常赞许地大的数字。,普通必须花费的钱要花很长时期。。

又,咱们可以悠闲地地发现物。,并非每个买卖都有10种选择,譬如只剩2建立的时辰至多正是2种选择。

是否状态有K(1)

只需应用下面应变量f。。

行为准则:

#includeusingnamespace std;int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};int num[14];voidf(int n){int r =0, s, e, m, k =0;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if((n >>(13- m))&1)r +=((n >>(13- s))&1)^((n >>(13- e))&1);}while(n){
		k += n &1;
		n /=2;}if(num[k]< r)num[k]= r;}intmain(){for(int i =0; i <14; i++)num[i]=0;for(int n =0; n <8192; n++)f(n);for(int i =2; i <=12; i++)cout << num[i]<<"  ";return0;}

运转成功实现的事:

2  4  7  7  9  10  9  9  8  6  4

2*4*7*7*9*10*9*9*8*6*4=548674560,因而无论哪些状态下。,停止吃水占先搜索的话,至多需求约5亿次数计算

计算性能在一秒钟内计算大概1亿次。,因而这次是可以接待的。。

七,处理原始成绩

声母的成绩是鉴于对白色子女的限度局限。,如下程序更为复杂。,但心不在焉必要布头。。

这样的事物,你可以经过吃水占先搜索来处理左右成绩。,同时,因状态的总共是稍许地的。,因而用静态放映记载方式来忍住反复任务。

行为准则:

#include#includeusingnamespace std;int r[8192][14];int st[16]={1,1,3,11,1,2,2,3,6,7,8,7,4,5,6,2};int en[16]={3,11,13,13,7,6,8,7,12,11,12,13,10,9,8,12};
stack<int>ans;boolf(int n,int k){if(n ==(n&-n))returntrue;if(r[n][k]<0)returnfalse;int s, e, m;for(int i =0; i <16; i++){
		s = st[i], e = en[i], m =(s + e)/2;if(m == k)continue;if(!((n >>(13- m))&1))continue;if(!(((n >>(13- s))&1)^((n >>(13- e))&1)))continue;int nn, kk = k, tem;if(k == s || k == e)kk = s + e - k;
		tem =(1<<(13- s))+(1<<(13- e));
		nn = n -(n&tem)+ tem -(n&tem)-(1<<(13- m));if(f(nn, kk)){
			ans.push(i);
			m =-1;break;}}if(m ==-1)returntrue;
	r[n][k]=-1;returnfalse;}intmain(){int n =0, k;
	cout <<按编号\n1    2    3\n  4    5\n6    7    8\n  9    10\n11   12   13\n";
	cout <<上上下下。,从左往右,移交出口每个点阵。\n1残忍的孩子。,0残忍的心不在焉孩子。,充足的都被间隔隔开了。\n";for(int i =1; i <=13; i++){
		cin >> k;
		n = n *2+ k;}
	cout <<"出口红子某种情势或位置格子的序号(1-13)\n";
	cin >> k;for(int i =0; i <8192; i++)for(int j =0; j <14; j++)r[i][j]=0;while(!ans.empty())ans.pop();f(n, k);
	cout <<"答案为:(党表现一任一某一买卖),每个行说话中肯2个积分的区别表现起源点和完毕点。\n";while(!ans.empty()){int i = ans.top();
		ans.pop();
		cout << st[i]<<"   "<< en[i]<< endl;}return0;}

示例:




发表评论

电子邮件地址不会被公开。 必填项已用*标注