HDU 5754 Life Winner Bo （各種博弈融合）
題目鏈接：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的棋盤(pán)，一共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.車(chē)的走法是橫向或豎向任意格，那么在對(duì)角線(xiàn)上必輸，因?yàn)橄仁肿呤裁床呗裕笫帜７录纯?，反之n!=m，先手只要使對(duì)方到對(duì)角線(xiàn)上即必勝。
???? 3.馬的走法和中國(guó)象棋是一樣的，日字形，馬比較特殊的是，會(huì)出現(xiàn)平局的情況，即誰(shuí)都不能到達(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.皇后的走法和王類(lèi)似，不過(guò)王后是走任意步，或者沿斜線(xiàn)任意步。這其實(shí)可以看成，兩堆石子，要么從一堆取任意個(gè)，要么從兩堆同時(shí)取相同任意個(gè)。這就是威佐夫博弈，可見(jiàn)這篇博客。
???? 這題綜合考察了幾種博弈，還是很不錯(cuò)的，沒(méi)有接觸過(guò)博弈的人，可以學(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;
} 
下載文檔
