HDU 5754 Life Winner Bo

时间：2023-03-08 15:37:07

四种棋子实质上都是一样的思路：

如果某位置的棋子，它下一步可以走到的位置中 能找到有后手胜的位置，那么该位置先手必胜。

如果某位置的棋子，它下一步可以走到的位置中 全是先手胜，那么该位置后手必胜。

其余三种都用如上思路打表即可，但要注意马的情况（因为马可能有些位置走不到终点）：

如果该位置走过去的两个位置都是平局的，那么该位置也是平局。

如果该位置走过去的两个位置都是先手胜，那么该位置后手胜。

如果该位置走过去的两个位置中有至少一个位置是后手胜，那么该位置先手胜。

其余情况，均为平局。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

const int maxn=;

int king[maxn][maxn],rook[maxn][maxn],knight[maxn][maxn],queen[maxn][maxn];

bool r[maxn],c[maxn],x[*maxn];

int check(int a,int b)

{

    if(a<=||a>) return -;

    if(b<=||b>) return -;

    return knight[a][b];

}

void init()

{

    memset(king,-,sizeof king);

    memset(rook,-,sizeof rook);

    memset(knight,-,sizeof knight);

    memset(queen,-,sizeof queen);

    king[][]=;

    for(int i=;i<=;i++) king[][i]=king[i][]=king[i-][]^;

    for(int i=;i<=;i++) for(int j=;j<=;j++)

        if(king[i][j-]==||king[i-][j]==||king[i-][j-]==) king[i][j]=; else king[i][j]=;

    memset(r,,sizeof r); memset(c,,sizeof c);

    rook[][]=; r[]=; c[]=;

    for(int i=;i<=;i++) rook[i][]=rook[][i]=;

    for(int i=;i<=;i++) for(int j=;j<=;j++)

        if(r[i]==||c[j]==) rook[i][j]=; else rook[i][j]=, r[i]=, c[j]=;

    knight[][]=;

    for(int i=;i<=;i++) for(int j=;j<=;j++)

    {

        if(check(i-,j-)==-&&check(i-,j-)==-) continue;

        if(check(i-,j-)==&&check(i-,j-)==) {knight[i][j]=; continue;}

        if(check(i-,j-)==||check(i-,j-)==) {knight[i][j]=; continue;}

        else continue;

    }

    memset(r,,sizeof r); memset(c,,sizeof c); memset(x,,sizeof x);

    queen[][]=; r[]=; c[]=; x[]=;

    for(int i=;i<=;i++) queen[i][]=queen[][i]=;

    for(int i=;i<=;i++) for(int j=;j<=;j++) {

        int num; if(i-min(i-,j-)==) num=j-min(i-,j-); else num=+i-min(i-,j-);

        if(r[i]==||c[j]==||x[num]==) queen[i][j]=; else queen[i][j]=, r[i]=, c[j]=, x[num]=;

    }

}

int main()

{

    init(); int T; scanf("%d",&T);

    while(T--)

    {

        int n,m,type,ans; scanf("%d%d%d",&type,&n,&m);

        if(type==) ans=king[n][m]; if(type==) ans=rook[n][m];

        if(type==) ans=knight[n][m]; if(type==) ans=queen[n][m];

        if(ans==) printf("G"); else if(ans==) printf("B"); else printf("D");

        printf("\n");

    }

    return ;

}

相关文章