題目鏈接：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格，或同時向下向右1格，即(x+1,y)/(x,y+1)/)(x+1,y+1)三種走法，遞推推一下即可。一個節(jié)點的后繼為必敗態(tài)，那么它為必勝態(tài)，如果一個節(jié)點的后繼全都是必勝態(tài)，那么它就是必敗態(tài)，按剩余步數(shù)，從小到大遞推一下即可。

???? 2.車的走法是橫向或豎向任意格，那么在對角線上必輸，因為先手走什么策略，后手模仿即可，反之n!=m，先手只要使對方到對角線上即必勝。

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

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

???? 這題綜合考察了幾種博弈，還是很不錯的，沒有接觸過博弈的人，可以學到很多。

代碼：

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