【BZOJ 3106】【CQOI 2013】棋盘游戏

本文主要是介绍【BZOJ 3106】【CQOI 2013】棋盘游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

貌似叫对抗搜索？其实应该和博弈论差不多吧，只不过博弈论是针对当前局面做出唯一判断，而对抗搜索是通过搜索加以决策。
对于本题，显然白棋腿短，如果第一步吃不掉黑棋就再也吃不到了，所以白棋的策略就是尽量拖延时间。
再来看黑棋，显然黑棋如果第一步不被吃掉是必胜的，因为黑棋会不断地缩小白棋的活动范围（换个方法想，黑棋腿长，一定不会输，又不会出现和棋局面，所以黑必胜），所以黑棋的策略是尽快吃掉白棋。
dfs(x,y,a,b,c,d)时，x=0表示白走，x=1表示黑走；y表示走了几步；a和b是白棋坐标；c和d是黑棋坐标。注意用数组存一下已经出现的状态。

#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 100000
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
int n,a,b,c,d;
int f[2][60][21][21][21][21];
int dfs(int x,int y,int a,int b,int c,int d)
{if (y > 3 * n) return inf;if (a == c && b == d) return x?inf:0;if (f[x][y][a][b][c][d]) return f[x][y][a][b][c][d];int ans;if (x)//黑棋的策略是尽快吃掉白棋，时间要短{ans = inf;if (c > 1) ans = min(ans,dfs(0,y+1,a,b,c-1,d));if (c > 2) ans = min(ans,dfs(0,y+1,a,b,c-2,d));if (c < n) ans = min(ans,dfs(0,y+1,a,b,c+1,d));if (c < n - 1) ans = min(ans,dfs(0,y+1,a,b,c+2,d));if (d > 1) ans = min(ans,dfs(0,y+1,a,b,c,d-1));if (d > 2) ans = min(ans,dfs(0,y+1,a,b,c,d-2));if (d < n) ans = min(ans,dfs(0,y+1,a,b,c,d+1));if (d < n - 1) ans = min(ans,dfs(0,y+1,a,b,c,d+2));}else//白棋的策略是尽量拖延时间，时间要长{ans = 0;if (a > 1) ans = max(ans,dfs(1,y+1,a-1,b,c,d));if (a < n) ans = max(ans,dfs(1,y+1,a+1,b,c,d));if (b > 1) ans = max(ans,dfs(1,y+1,a,b-1,c,d));if (b < n) ans = max(ans,dfs(1,y+1,a,b+1,c,d));}ans++;f[x][y][a][b][c][d] = ans;return ans;
}
int main()
{scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);if (abs(a-c) + abs(b-d) <= 1) printf("WHITE 1\n");else printf("BLACK %d\n",dfs(0,0,a,b,c,d));return 0;
}