3130: [Sdoi2013]费用流
3119: Book

3106: [cqoi2013]棋盘游戏

高橋直樹 posted @ 2013年4月16日 14:57 in BZOJ with tags bzoj CQOI , 1022 阅读

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391578 Liu_Ts 3106 Accepted 96528 kb 5728 ms C++ 1294 B 2013-04-16 13:10:46

 

题意

一个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]);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter