Description
一个\(n \times n（n \le 2）\)棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。
A的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。 B的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。 和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。你的任务是判断谁会赢，需要多少回合。 比如\(n=2\)，白棋子在\((1,1)\)，黑棋子在\((2,2)\)，那么虽然A有两种走法，第二个回合B总能取胜。
Input
输入仅一行，包含五个整数\(n, r_{1}, c_{1}, r_{2}, c_{2}\)，即棋盘大小和棋子位置。白色棋子在\((r_{1},c_{1})\)，黑色棋子在\((r_{2},c_{2})（1 \le r_{1},c_{1},r_{2},c_{2} \le n）\)。黑白棋子的位置保证不相同。
Output
输出仅一行，即游戏结果。如果A获胜，输出WHITE \(x\)；如果B获胜，输出BLACK \(x\)；如果二者都没有必胜策略，输出DRAW。
Sample Input
2 1 1 2 2
Sample Output
BLACK 2
HINT
\(n \le 20\)
首先有个结论可以判胜负：
如果A与B只相差一格，那么A一定获胜；否则B一定获胜。那个平局只是来卖个萌的。(B走的快一些) 然后就是求合法的步数了，这个是CLB告诉我的极大极小搜索。 我开始裸搜果断TLE，加了记忆化，果断WA，没怎么打过，怎么调也调不对，最后还是参照了别人的程序长了见识。#include#include #include #include using namespace std;#define inf (1<<30)#define lim (3*n+2)#define maxn (25)const int xx[] = {0,1,0,-1},yy[] = {1,0,-1,0};int n,X1,X2,Y1,Y2,ans; int vis[maxn][maxn][maxn][maxn][maxn*3][2];inline bool okay(int x,int y) { return x > 0&&x<=n&&y > 0&&y<=n; }inline int dfs(bool now,int a1,int b1,int a2,int b2,int step){ if (step > lim) return inf; if (vis[a1][b1][a2][b2][step][now]) return vis[a1][b1][a2][b2][step][now]; else if (a1 == a2&&b1 == b2) { if (now) return inf; return 0; } int ret; if (!now) { ret = 0; for (int i = 0;i < 4;++i) if (okay(a1+xx[i],b1+yy[i])) ret = max(dfs(now^1,a1+xx[i],b1+yy[i],a2,b2,step+1),ret); } else { ret = inf; for (int j = 1;j <= 2;++j) for (int i = 0;i < 4;++i) if (okay(a2+j*xx[i],b2+j*yy[i])) ret = min(dfs(now^1,a1,b1,a2+j*xx[i],b2+j*yy[i],step+1),ret); } return vis[a1][b1][a2][b2][step][now] = ++ret;}int main(){ freopen("3106.in","r",stdin); freopen("3106.out","w",stdout); scanf("%d %d %d %d %d\n",&n,&X1,&Y1,&X2,&Y2); if (abs(X1-X2)+abs(Y1-Y2) == 1) printf("WHITE 1"); else { printf("BLACK "); printf("%d",dfs(0,X1,Y1,X2,Y2,0)); } fclose(stdin); fclose(stdout); return 0;}