题解 P4576 【[CQOI2013]棋盘游戏】

JRhdj · 2018-08-16 09:31:50 · 题解

据说这叫对抗搜索，本质上就是博弈论嘛

只是博弈论是在某一步直接作出决策

由题意除非黑棋是在白棋1步范围以内，否则白棋不可能获胜。那么我们需要做的就是让黑棋尽量快的获胜，白棋尽量多苟一会，那么就可以转移了。

状态用f(x,y,r1,c1,r2,c2)表示，x=(0/1)表示黑白棋，y是步数，(r1,c1)是白棋坐标，（r2,c2）是黑棋坐标

// luogu-judger-enable-o2
#include <cstdio>
#include <cmath> 
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1e9+7;
const int M = 25;
int n, r1, c1, r2, c2, ans;
int f[2][60][M][M][M][M]; 
int dfs(int x, int y, int r1, int c1, int r2, int c2)
{
    int ans;
    if(y>3*n) return inf;
    if(f[x][y][r1][c1][r2][c2]) return f[x][y][r1][c1][r2][c2];
    if(r1 == r2 && c1 == c2) return x?inf:0;
    if(!x)
    {   
        ans = 0;
        if(r1>1) ans = max(ans, dfs(1, y+1, r1-1, c1, r2, c2));
        if(r1<n) ans = max(ans, dfs(1, y+1, r1+1, c1, r2, c2));
        if(c1>1) ans = max(ans, dfs(1, y+1, r1, c1-1, r2, c2));
        if(c1<n) ans = max(ans, dfs(1, y+1, r1, c1+1, r2, c2));
    }
    else
    {
        ans = inf;
        if(r2>1) ans = min(ans, dfs(0, y+1, r1, c1, r2-1, c2));
        if(r2>2) ans = min(ans, dfs(0, y+1, r1,c1, r2-2, c2));
        if(r2<n) ans = min(ans, dfs(0, y+1, r1, c1, r2+1, c2));
        if(r2<n-1) ans = min(ans, dfs(0, y+1, r1, c1, r2+2, c2));
        if(c2>1) ans = min(ans, dfs(0, y+1, r1, c1, r2, c2-1));
        if(c2>2) ans = min(ans, dfs(0, y+1, r1, c1, r2, c2-2));
        if(c2<n) ans = min(ans, dfs(0, y+1, r1, c1, r2, c2+1));
        if(c2<n-1) ans = min(ans, dfs(0, y+1, r1, c1, r2, c2+2));
    }
    f[x][y][r1][c1][r2][c2] = ++ans;//cout<<x<<y<<r1<<c1<<r2<<c2<<"  "<<f[x][y][r1][c1][r2][c2]<<"Ans="<<ans<<endl;;
    return ans;
}
int main()
{
    scanf("%d%d%d%d%d", &n, &r1, &c1, &r2, &c2);
    //cout<<abs(r1-r2)+abs(c1-c2)<<endl;
    if(abs(r1-r2)+abs(c1-c2) <= 1) printf("WHITE 1\n");
    else printf("BLACK %d\n", dfs(0, 0, r1, c1, r2, c2));
    return 0;
}