Accepted/96992 kb/5576 ms

bzoj3106.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=21;
int f[maxn][maxn][maxn][maxn][maxn*3][2];
int n;
int abs(int a)
{
	return a>0?a:-a;
}
int dfs(int a,int b,int c,int d,int dep,int t)
{
	if (dep>3*n)
		return 324343546;
	if (f[a][b][c][d][dep][t])
		return f[a][b][c][d][dep][t];
	if (a==c && b==d)
		return t*453431224;
	int &ans=f[a][b][c][d][dep][t];
	if(!t)
	{
		if (a>1)
			ans=max(ans,dfs(a-1,b,c,d,dep+1,!t)+1);
		if (a<n)
			ans=max(ans,dfs(a+1,b,c,d,dep+1,!t)+1);
		if (b>1)
			ans=max(ans,dfs(a,b-1,c,d,dep+1,!t)+1);
		if (b<n)
			ans=max(ans,dfs(a,b+1,c,d,dep+1,!t)+1);
	}else
	{
		ans=233333333;
		if (c>1)
			ans=min(ans,dfs(a,b,c-1,d,dep+1,!t)+1);
		if (c>2)
			ans=min(ans,dfs(a,b,c-2,d,dep+1,!t)+1);
		if (c<n)
			ans=min(ans,dfs(a,b,c+1,d,dep+1,!t)+1);
		if (c<n-1)
			ans=min(ans,dfs(a,b,c+2,d,dep+1,!t)+1);
		if (d>1)
			ans=min(ans,dfs(a,b,c,d-1,dep+1,!t)+1);
		if (d>2)
			ans=min(ans,dfs(a,b,c,d-2,dep+1,!t)+1);
		if (d<n)
			ans=min(ans,dfs(a,b,c,d+1,dep+1,!t)+1);
		if (d<n-1)
			ans=min(ans,dfs(a,b,c,d+2,dep+1,!t)+1);
	}
	return ans;
}
int main()
{
	int a,b,c,d;
	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]);
	}
	return 0;
}