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;}

示例:




发表评论

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