【BZOJ 3106】 3106: [cqoi2013]棋盘游戏（对抗搜索）

3106: [cqoi2013]棋盘游戏

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 544  Solved: 233

Description

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

l         A的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。

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

和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。你的任务是判断谁会赢，需要多少回合。

比如n=2，白棋子在(1,1)，黑棋子在(2,2)，那么虽然A有两种走法，第二个回合B总能取胜。

Input

输入仅一行，包含五个整数n, r1, c1, r2, c2，即棋盘大小和棋子位置。白色棋子在(r1,c1)，黑色棋子在(r2,c2)（1<=r1,c1,r2,c2<=n）。黑白棋子的位置保证不相同。

Output

输出仅一行，即游戏结果。如果A获胜，输出WHITE x；如果B获胜，输出BLACK x；如果二者都没有必胜策略，输出DRAW。

Sample Input

2 1 1 2 2

Sample Output

BLACK 2

HINT

n<=20

Source

【分析】

　　BLACK腿长所以能赢？

　　只有WHITE第一步能赢才能赢。

　　后面的事情，直接随便搜搜就好了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define INF 0xfffffff

 int f[][][][][][];

 int n;

 int ffind(int p,int x,int r1,int c1,int r2,int c2)

 {

     if(x>*n) return INF;

     if(r1==r2&&c1==c2) return p?INF:;

     if(f[p][x][r1][c1][r2][c2]) return f[p][x][r1][c1][r2][c2];

     int ans;

     if(p)

     {

         ans=INF;

         if(r2>) ans=min(ans,ffind(p^,x+,r1,c1,r2-,c2));

         if(r2>) ans=min(ans,ffind(p^,x+,r1,c1,r2-,c2));

         if(c2>) ans=min(ans,ffind(p^,x+,r1,c1,r2,c2-));

         if(c2>) ans=min(ans,ffind(p^,x+,r1,c1,r2,c2-));

         if(r2<n) ans=min(ans,ffind(p^,x+,r1,c1,r2+,c2));

         if(r2+<n) ans=min(ans,ffind(p^,x+,r1,c1,r2+,c2));

         if(c2<n) ans=min(ans,ffind(p^,x+,r1,c1,r2,c2+));

         if(c2+<n) ans=min(ans,ffind(p^,x+,r1,c1,r2,c2+));

     }

     else

     {

         ans=;

         if(r1>) ans=max(ans,ffind(p^,x+,r1-,c1,r2,c2));

         if(c1>) ans=max(ans,ffind(p^,x+,r1,c1-,r2,c2));

         if(r1<n) ans=max(ans,ffind(p^,x+,r1+,c1,r2,c2));

         if(c1<n) ans=max(ans,ffind(p^,x+,r1,c1+,r2,c2));

     }

     ans++;

     f[p][x][r1][c1][r2][c2]=ans;

     return ans;

 }

 int main()

 {

     int r1,c1,r2,c2;

     memset(f,,sizeof(f));

     scanf("%d%d%d%d%d",&n,&r1,&c1,&r2,&c2);

     if((abs(r1-r2)+abs(c1-c2))<=) printf("WHITE 1\n");

     else printf("BLACK %d\n",ffind(,,r1,c1,r2,c2));

     return ;

 }

2017-04-11 20:13:55

巴特西

【BZOJ 3106】 3106: [cqoi2013]棋盘游戏（对抗搜索）

3106: [cqoi2013]棋盘游戏

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

【BZOJ 3106】 3106: [cqoi2013]棋盘游戏 （对抗搜索）

3106: [cqoi2013]棋盘游戏

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

【BZOJ 3106】 3106: [cqoi2013]棋盘游戏（对抗搜索）