當(dāng)前位置:首頁 > 芯聞號 > 充電吧
[導(dǎo)讀]題目鏈接:HDU 5754 題面: Life Winner Bo Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 131072/13

題目鏈接:HDU 5754


題面:

Life Winner Bo Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 827????Accepted Submission(s): 309


Problem Description Bo is a "Life Winner".He likes playing chessboard games with his girlfriend G.

The size of the chessboard is N×M.The top left corner is numbered(1,1) and the lower right corner is numberd (N,M).

For each game,Bo and G take turns moving a chesspiece(Bo first).At first,the chesspiece is located at (1,1).And the winner is the person who first moves the chesspiece to (N,M).At one point,if the chess can't be moved and it isn't located at (N,M),they end in a draw.

In general,the chesspiece can only be moved right or down.Formally,suppose it is located at (x,y),it can be moved to the next point (x′,y′) only if x′≥x and y′≥y.Also it can't be moved to the outside of chessboard.

Besides,There are four kinds of chess(They have movement rules respectively).

1.king.

2.rook(castle).

3.knight.

4.queen.

(The movement rule is as same as the chess.)

For each type of chess,you should find out that who will win the game if they both play in an optimal strategy.

Print the winner's name("B" or "G") or "D" if nobody wins the game. ?
Input In the first line,there is a number T as a case number.

In the next T lines,there are three numbers type,N and M.

"type" means the kind of the chess.

T≤1000,2≤N,M≤1000,1≤type≤4 ?
Output For each question,print the answer. ?
Sample Input
4
1 5 5
2 5 5
3 5 5
4 5 5

?

Sample Output
G
G
D
B

?

Source 2016 Multi-University Training Contest 3


題意:

???? 給定N*M的棋盤,一共4顆棋子,每次一種1顆棋子,從左上角出發(fā),到右下角的人獲勝。


解題:

??? 1.王的走法是向下向右1格,或同時(shí)向下向右1格,即(x+1,y)/(x,y+1)/)(x+1,y+1)三種走法,遞推推一下即可。一個(gè)節(jié)點(diǎn)的后繼為必?cái)B(tài),那么它為必勝態(tài),如果一個(gè)節(jié)點(diǎn)的后繼全都是必勝態(tài),那么它就是必?cái)B(tài),按剩余步數(shù),從小到大遞推一下即可。

???? 2.車的走法是橫向或豎向任意格,那么在對角線上必輸,因?yàn)橄仁肿呤裁床呗裕笫帜7录纯?,反之n!=m,先手只要使對方到對角線上即必勝。

???? 3.馬的走法和中國象棋是一樣的,日字形,馬比較特殊的是,會(huì)出現(xiàn)平局的情況,即誰都不能到達(dá)(n,m),馬的遞推是,如果后繼中有必?cái)B(tài),那么當(dāng)前節(jié)點(diǎn)是必勝態(tài),如果后繼中都是必勝態(tài),那么當(dāng)前節(jié)點(diǎn)是必?cái)B(tài),如果后繼中有平局,那么當(dāng)前節(jié)點(diǎn)即為平局。(以上推導(dǎo)嚴(yán)格有序,即在排除了前一種情況的前提下成立)。

??? 4.皇后的走法和王類似,不過王后是走任意步,或者沿斜線任意步。這其實(shí)可以看成,兩堆石子,要么從一堆取任意個(gè),要么從兩堆同時(shí)取相同任意個(gè)。這就是威佐夫博弈,可見這篇博客。

???? 這題綜合考察了幾種博弈,還是很不錯(cuò)的,沒有接觸過博弈的人,可以學(xué)到很多。


代碼:

#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;
bool king[1005][1005];
int horse[1005][1005];
bool vis[1005][1005];
int main()
{
	int t,type,n,m,s1,s2;
	memset(king,0,sizeof(king));
	king[0][0]=0;
	for(int i=0;i<=1000;i++)
	{
		for(int j=0;j<=1000;j++)
		{
			if(king[i][j]==0)
			{
				if(i+1<=1000)
				    king[i+1][j]=1;
				if(j+1<=1000)
					king[i][j+1]=1;
                if(i+1<=1000&&j+1<=1000)
					king[i+1][j+1]=1;
			}
		}
	}
    memset(horse,-1,sizeof(horse));
	horse[0][0]=0;
	for(int i=0;i<=1000;i++)
	{
		for(int j=0;j<=1000;j++)
		{
			s1=-2;s2=-2;
		   if(i-1>=0&&j-2>=0)
              s1=horse[i-1][j-2];
		   if(i-2>=0&&j-1>=0)
			  s2=horse[i-2][j-1];
           if(s1!=-2&&s2!=-2)
		   {
			   if(s1==0||s2==0)
				   horse[i][j]=1;
			   else if(s1==-1||s2==-1)
				   horse[i][j]=-1;
			   else
				   horse[i][j]=0;
		   }
		   if(s1!=-2||s2!=-2)
		   {
			   if(s1==0||s2==0)
				   horse[i][j]=1;
			   else if(s1==-1||s2==-1)
				   horse[i][j]=-1;
			   else
				   horse[i][j]=0;
		   }
		  
		}
	}
	scanf("%d",&t);
    while(t--)
	{
		int flag;
		scanf("%d%d%d",&type,&n,&m);
		if(type==1)
		{
			if(king[n-1][m-1]==1)
				flag=1;
			else
				flag=0;
		}
		else if(type==2)
		{
			if(n==m)
				flag=0;
			else
				flag=1;
		}
		else if(type==3)
		{
			n--;
			m--;
			if(horse[n][m]==-1)
				flag=2;
			else if(horse[n][m])
				flag=1;
			else
				flag=0;
		}
		else
		{
			int dif,tmp;
			n--;
			m--;
			if(n>m)
				swap(n,m);
		    dif=m-n;
			tmp=dif*(1.0+sqrt(5.0))/2;
			if(n==tmp)
				flag=0;
			else
				flag=1;
		}
		if(flag==2)
			printf("Dn");
		else if(flag==1)
			printf("Bn");
		else
			printf("Gn");
	}
	return 0;
}



本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉