好久没写oi系列的题解了

要不是为了大作业我才不会回来学这些奇怪的东西呢

本题对抗搜索就好啦

首先要分析一点，就是由于我们的黑棋每次走两步，白棋只走一步而且是白棋先走，所以除非白棋第一步吃掉黑棋，否则黑棋必胜

接下来就是计算黑棋如何取胜的问题了

首先简单介绍一下对抗搜索

我们知道，两个人下棋，两个人都想赢（或者至少不想输得那么惨），那么这个问题可以转化成——第一个人想赢，而第二个人想让第一个人输（或者赢得不容易）

这就是对抗搜索得思想：如果我们对每个局面给出一个估值，估值越大表示第一个人越优，那么在第一个人下棋的时候，他的目的是要使当前局面的估值最大

而对第二个人而言，他的目的是使当前局面的估值最小

于是我们利用dfs+记忆化来实现就可以了

注意这里反一下，黑棋要使自己的步数最小

这里记忆化要记录步数，其原因是有可能这两个人出现来回交换位置转圈的情况，这种情况要通过步数来区分

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10 const int inf=1e9;
11 int x1,x2,yy,y2;
12 int n;
13 int to[9][2]={{0,0},{1,0},{0,1},{-1,0},{0,-1},{2,0},{0,2},{-2,0},{0,-2}};
14 int ret[21][21][21][21][61][2];
15 bool check(int x,int y)
16 {
17 return x>0&&x<=n&&y>0&&y<=n; 18 } 19 int dfs(int xw,int yw,int xb,int yb,int typ,int dep)//typ=1表示黑棋走，typ=0表示白棋走 20 { 21 if(dep>3*n)return inf;
22 if(ret[xw][yw][xb][yb][dep][typ])return ret[xw][yw][xb][yb][dep][typ];
23 if(xw==xb&&yw==yb)
24 {
25 if(typ)return inf;
26 else return 0;
27 }
28 int temp=typ?inf:0;
29 if(typ)
30 {
31 for(int i=1;i<=8;i++)
32 {
33 int tx=xb+to[i][0],ty=yb+to[i][1];
34 if(check(tx,ty))temp=min(temp,dfs(xw,yw,tx,ty,typ^1,dep+1));
35 }
36 }else
37 {
38 for(int i=1;i<=4;i++)
39 {
40 int tx=xw+to[i][0],ty=yw+to[i][1];
41 if(check(tx,ty))temp=max(temp,dfs(tx,ty,xb,yb,typ^1,dep+1));
42 }
43 }
44 return ret[xw][yw][xb][yb][dep][typ]=temp+1;
45 }
46 int main()
47 {
48 scanf("%d%d%d%d%d",&n,&x1,&yy,&x2,&y2);
49 if(abs(x2-x1)+abs(y2-yy)<=1){printf("WHITE 1\n");return 0;}
50 else printf("BLACK %d\n",dfs(x1,yy,x2,y2,0,1));
51 return 0;
52 }

当然，这里也可以使用$\alpha$-$\beta$剪枝，其原理如下：

考虑一个黑棋下的局面，我们知道他的前一手和后一手都是白棋要下的（废话）

如果这个局面有一个发展使得黑棋可以以a步抓到白棋，那么这个局面黑棋取胜所需的最多步数即为$a$

可是我们知道，对于当前局面的上一层，是一个白棋的局面，他想最大化黑棋的步数，假设白棋已经搜到的前几个局面之中黑棋最大的步数是$b$

那我们可以发现，如果$a<b$，那么无论当前局面如何发展，白棋都不会容许走到当前局面（思考一下：当双方均采用最优策略时，如果进入这个局面，黑棋至多只需要$a$步就能取胜，而如果不进入这个局面，黑棋至少需要$b$步才能取胜，所以白棋一定不会允许黑棋进入这个局面，也即我们不再需要了解这个局面接下来会如何演变，因为白棋一定不会选择这个局面！）

于是同理考虑一个白棋下的情况，同样进行剪枝就可以了

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10 const int inf=1e9;
11 int x1,x2,yy,y2;
12 int n;
13 int to[9][2]={{0,0},{1,0},{0,1},{-1,0},{0,-1},{2,0},{0,2},{-2,0},{0,-2}};
14 int ret[21][21][21][21][61][2];
15 bool used[21][21][21][21][61][2];
16 bool check(int x,int y)
17 {
18 return x>0&&x<=n&&y>0&&y<=n; 19 } 20 int dfs(int xw,int yw,int xb,int yb,int typ,int dep,int lasxw,int lasyw,int lasxb,int lasyb)//typ=1表示黑棋走，typ=0表示白棋走 21 { 22 if(dep>3*n)return inf;
23 if(ret[xw][yw][xb][yb][dep][typ]&&!used[xw][yw][xb][yb][dep][typ])return ret[xw][yw][xb][yb][dep][typ];
24 if(xw==xb&&yw==yb)
25 {
26 if(typ)return inf;
27 else return 0;
28 }
29 int temp=typ?inf:0;
30 ret[xw][yw][xb][yb][dep][typ]=temp;
31 if(typ)
32 {
33 for(int i=1;i<=8;i++) 34 { 35 int tx=xb+to[i][0],ty=yb+to[i][1]; 36 if(check(tx,ty))temp=min(temp,dfs(xw,yw,tx,ty,typ^1,dep+1,xw,yw,xb,yb)); 37 ret[xw][yw][xb][yb][dep][typ]=temp+1; 38 if(temp+1ret[lasxw][lasyw][lasxb][lasyb][dep-1][typ^1]&&dep!=1){used[xw][yw][xb][yb][dep][typ]=1;return temp+1;}
48 }
49 }
50 used[xw][yw][xb][yb][dep][typ]=0;
51 return ret[xw][yw][xb][yb][dep][typ]=temp+1;
52 }
53 int main()
54 {
55 scanf("%d%d%d%d%d",&n,&x1,&yy,&x2,&y2);
56 if(abs(x2-x1)+abs(y2-yy)<=1){printf("WHITE 1\n");return 0;}
57 else printf("BLACK %d\n",dfs(x1,yy,x2,y2,0,1,0,0,0,0));
58 return 0;
59 }

其实你会发现，剪枝的版本比不剪枝的版本还要慢，究其原因，在于我们剪枝让一部分记忆化失效了，这样反而增加了用时

如果用下面的写法就可以回避这个问题，但是由于增加了一个数组会造成mle

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=1e9;
int x1,x2,yy,y2;
int n;
int to[9][2]={{0,0},{1,0},{0,1},{-1,0},{0,-1},{2,0},{0,2},{-2,0},{0,-2}};
int ret[21][21][21][21][61][2];
int used[21][21][21][21][61][2];
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)
{
return x0&&x<=n&&y>0&&y<=n; } int dfs(int xw,int yw,int xb,int yb,int typ,int dep,int lasxw,int lasyw,int lasxb,int lasyb)//typ=1表示黑棋走，typ=0表示白棋走 { if(dep>3*n)return inf;
if(ret[xw][yw][xb][yb][dep][typ]&&!used[xw][yw][xb][yb][dep][typ])return ret[xw][yw][xb][yb][dep][typ];
if(xw==xb&&yw==yb)
{
if(typ)return inf;
else return 0;
}
int temp=typ?inf:0;
if(!ret[xw][yw][xb][yb][dep][typ])ret[xw][yw][xb][yb][dep][typ]=temp;
if(typ)
{
for(int i=used[xw][yw][xb][yb][dep][typ]+1;i<=8;i++) { int tx=xb+to[i][0],ty=yb+to[i][1]; if(check(tx,ty)){int t=dfs(xw,yw,tx,ty,typ^1,dep+1,xw,yw,xb,yb);temp=min(temp,t);} ret[xw][yw][xb][yb][dep][typ]=min(ret[xw][yw][xb][yb][dep][typ],temp+1); if(temp+1ret[lasxw][lasyw][lasxb][lasyb][dep-1][typ^1]&&dep!=1){used[xw][yw][xb][yb][dep][typ]=i;return temp+1;}
}
}
used[xw][yw][xb][yb][dep][typ]=0;
return ret[xw][yw][xb][yb][dep][typ];
}
int main()
{
scanf("%d%d%d%d%d",&n,&x1,&yy,&x2,&y2);
if(abs(x2-x1)+abs(y2-yy)<=1){printf("WHITE 1\n");return 0;}
else printf("BLACK %d\n",dfs(x1,yy,x2,y2,0,1,0,0,0,0));
return 0;
}