HDU 5754 Life Winner Bo

Posted on | In | 阅读

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

1
2
3
4
5
4
1 5 5
2 5 5
3 5 5
4 5 5

Sample Output

1
2
3
4
G
G
D
B

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int dp1[1005][1005];
int dp3[1005][1005];
int dp4[1005][1005];

void init()
{
    for(int i = 0; i <= 1000; i++)
    {
        dp1[i][1001] = dp1[1001][i] = 1;
        dp3[i][1000] = dp3[1000][i] = 3;
        dp3[i][1001] = dp3[1001][i] = 1;
        dp4[i][i] = dp4[i][1000] = dp4[1000][i] = 1;
        dp4[i][1001] = dp4[1001][i] = 1;
    }
    dp3[1000][1000] = 0;
    dp3[999][999] = 3;
    dp1[1000][1000] = dp4[1000][1000] = 0;
    dp1[1001][1001] = dp4[1001][1001] = 1;

    for(int i = 1000; i >= 0; i--)
    {
        for(int j = 1000; j >= 0; j--)
        {
            if(dp1[i+1][j] == 1 && (dp1[i][j+1] == 1 && dp1[i+1][j+1] == 1))
                dp1[i][j] = 0;
            else
                dp1[i][j] = 1;
        }
    }

    for(int i = 999; i >= 0; i--)
    {
        for(int j = 999; j >= 0; j--)
        {
            if(i == 999 && j == 999){}
            else if((i == 999 || dp3[i+2][j+1] == 1) && (j == 999 || dp3[i+1][j+2] == 1))
                dp3[i][j] = 0;
            else if(dp3[i+2][j+1] == 0 || dp3[i+1][j+2] == 0)
                dp3[i][j] = 1;
            else
                dp3[i][j] = 3;


            if(dp4[i][j]) continue;
            if(!dp4[i][j])
            {
                for(int ii = i - 1; ii >= 0; ii--)
                    dp4[ii][j] = 1;
                for(int ii = j - 1; ii >= 0; ii--)
                    dp4[i][ii] = 1;
                for(int ii = 1; i-ii >= 0 && j-ii >= 0; ii++)
                    dp4[i-ii][j-ii] = 1;
            }
        }
    }


}

int main()
{
    int ca;
    int t, n, m;
    memset(dp1, 0, sizeof(dp1));
    memset(dp3, 0, sizeof(dp3));
    memset(dp4, 0, sizeof(dp4));
    init();
    scanf("%d", &ca);
    while(ca--)
    {

        scanf("%d%d%d", &t, &n, &m);
        if(t == 1)
        {
            if(dp1[1000-n+1][1000-m+1])
                printf("B\n");
            else
                printf("G\n");
        }
        else if(t == 2)
        {
            if((n-1) ^ (m-1))
                printf("B\n");
            else
                printf("G\n");
        }
        else if(t == 3)
        {
            if(dp3[1000-n+1][1000-m+1] == 1)
                printf("B\n");
            else if(dp3[1000-n+1][1000-m+1] == 0)
                printf("G\n");
            else if(dp3[1000-n+1][1000-m+1] == 3)
                printf("D\n");

        }
        else
        {
            if(dp4[1000-n+1][1000-m+1] == 1)
                printf("B\n");
            else
                printf("G\n");
        }
    }
    return 0;
}