Description

一個\(n \times n（n \le 2）\)棋盤上有黑白棋子各一枚。游戲者A和B輪流移動棋子，A先走。
A的移動規(guī)則：只能移動白棋子?？梢酝舷伦笥宜膫€方向之一移動一格。
B的移動規(guī)則：只能移動黑棋子?？梢酝舷伦笥宜膫€方向之一移動一格或者兩格。
和通常的“吃子”規(guī)則一樣，當某游戲者把自己的棋子移動到對方棋子所在的格子時，他就贏了。兩個游戲者都很聰明，當可以獲勝時會盡快獲勝，只能輸掉的時候會盡量拖延時間。你的任務是判斷誰會贏，需要多少回合。
比如\(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<iostream> #include<cmath> #include<cstdio> #include<cstdlib> 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; }

轉載于:https://www.cnblogs.com/mmlz/p/4306236.html

總結

以上是生活随笔為你收集整理的BZOJ 3106 棋盘游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。