http://www.lydsy.com/JudgeOnline/problem.php?id=3106

题意

一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。

        A：移动白棋子。可以往上下左右四个方向之一移动一格。

        B：移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

当某游戏者把自己的棋子移动到对方棋子所在的格子时就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。判断谁会赢，需要多少回合。

题解

不看题解不会- =

然后找到一种很奇怪的做法。。

首先没有平局- =，

如果黑色不在白色的旁边，黑色一定赢（因为白色永远吃不到它0.0）。

接下来的问题是求需要多少步

暴力，然后，其实是卡时。。

我们猜测答案不超过3n步。。。。

记忆化搜索，f[a][b][c][d][x][y]表示白(a,b)，黑(c,d)，x步，y表示当前游戏者是谁。

于是就过了，不明真相。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=21;
int f[N][N][N][N][N*3][2],n,a,b,c,d;
int DFS(int a,int b,int c,int d,int x,int y)
{
    if(x>3*n)  return 1<<30;
    if(a==c&&b==d)  return y==1?1<<30:0;
    if(f[a][b][c][d][x][y])  return f[a][b][c][d][x][y];
    int &ans=f[a][b][c][d][x][y];
    if(y==0)
    {
        if(a>1)  ans=max(ans,DFS(a-1,b,c,d,x+1,1)+1);
        if(b>1)  ans=max(ans,DFS(a,b-1,c,d,x+1,1)+1);
        if(a<n)  ans=max(ans,DFS(a+1,b,c,d,x+1,1)+1);
        if(b<n)  ans=max(ans,DFS(a,b+1,c,d,x+1,1)+1);
    }
    else
    {
        ans=1<<30;
        if(c>1)  ans=min(ans,DFS(a,b,c-1,d,x+1,0)+1);
        if(d>1)  ans=min(ans,DFS(a,b,c,d-1,x+1,0)+1);
        if(c<n)  ans=min(ans,DFS(a,b,c+1,d,x+1,0)+1);
        if(d<n)  ans=min(ans,DFS(a,b,c,d+1,x+1,0)+1);
        if(c>2)  ans=min(ans,DFS(a,b,c-2,d,x+1,0)+1);
        if(d>2)  ans=min(ans,DFS(a,b,c,d-2,x+1,0)+1);
        if(c+2<=n)  ans=min(ans,DFS(a,b,c+2,d,x+1,0)+1);
        if(d+2<=n)  ans=min(ans,DFS(a,b,c,d+2,x+1,0)+1);
    }
    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 DFS(a,b,c,d,0,0),printf("BLACK %d\n",f[a][b][c][d][0][0]);
}