bzoj 3106

好久没写oi系列的题解了

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

本题对抗搜索就好啦

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

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

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

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

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

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

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

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

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

 1 #include <cstdio>

 2 #include <cmath>

 3 #include <cstring>

 4 #include <cstdlib>

 5 #include <iostream>

 6 #include <algorithm>

 7 #include <queue>

 8 #include <stack>

 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 <cstdio>

 2 #include <cmath>

 3 #include <cstring>

 4 #include <cstdlib>

 5 #include <iostream>

 6 #include <algorithm>

 7 #include <queue>

 8 #include <stack>

 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+1<ret[lasxw][lasyw][lasxb][lasyb][dep-1][typ^1]&&dep!=1){used[xw][yw][xb][yb][dep][typ]=1;return temp+1;}

39         }

40     }else

41     {

42         for(int i=1;i<=4;i++)

43         {

44             int tx=xw+to[i][0],ty=yw+to[i][1];

45             if(check(tx,ty))temp=max(temp,dfs(tx,ty,xb,yb,typ^1,dep+1,xw,yw,xb,yb));

46             ret[xw][yw][xb][yb][dep][typ]=temp+1;

47             if(temp+1>ret[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 <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

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 x<y?x:y;

}

bool check(int x,int y)

{

    return x>0&&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+1<ret[lasxw][lasyw][lasxb][lasyb][dep-1][typ^1]&&dep!=1){used[xw][yw][xb][yb][dep][typ]=i;return temp+1;}

        }

    }else

    {

        for(int i=used[xw][yw][xb][yb][dep][typ]+1;i<=4;i++)

        {

            int tx=xw+to[i][0],ty=yw+to[i][1];

            if(check(tx,ty)){int t=dfs(tx,ty,xb,yb,typ^1,dep+1,xw,yw,xb,yb);temp=max(temp,t);}

            ret[xw][yw][xb][yb][dep][typ]=max(ret[xw][yw][xb][yb][dep][typ],temp+1);

            if(temp+1>ret[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;

}

巴特西

bzoj 3106

最新文章

热门文章