NC19930. [CQOI2013]棋盘游戏
描述
输入描述
输入仅一行，包含五个整数n, r1, c1, r2, c2，即棋盘大小和棋子位置。白色棋子在(r1,c1)，黑色棋子在(r2,c2)（1 ≤ r1,c1,r2,c2 ≤ n）。黑白棋子的位置保证不相同。
输出描述
输出仅一行，即游戏结果。如果A获胜，输出WHITE x；如果B获胜，输出BLACK x；如果二者都没有必胜策略，输出DRAW。
示例1
输入:
2 1 1 2 2
输出:
BLACK 2
C++(clang++11) 解法, 执行用时: 791ms, 内存消耗: 81912K, 提交时间: 2021-02-14 12:39:18
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=1<<28;
int f[21][21][21][21][61][2];
int yh[10]={-1,0,1,0,-2,0,2,0};
int yl[10]={0,1,0,-1,0,2,0,-2};
int n,x,y,X,Y;
int dfs(int x,int y,int X,int Y,int c,int op)
{
int &g=f[x][y][X][Y][c][op];
if(x==X&&y==Y)
return op*inf;
if(c>3*n)
return inf;
if(g)
return g;
g=op*inf;
for(int i=0;i<(op?8:4);i++)
{
int tx=x+yh[i],ty=y+yl[i];
if(tx<1||tx>n||ty<1||ty>n)
continue;
if(!op)
g=max(g,dfs(X,Y,tx,ty,c+1,1));
else
g=min(g,dfs(X,Y,tx,ty,c+1,0));
}
return ++g;
}
int main()
{
scanf("%d %d %d %d %d",&n,&x,&y,&X,&Y);
if(abs(x-X)+abs(y-Y)<=1)
return puts("WHITE 1"),0;
printf("BLACK %d",dfs(x,y,X,Y,0,0));
}