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

【分析】

　　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