ACM 2017 南宁区域赛 Rake it in(对抗搜索)-白红宇

ACM 2017 南宁区域赛 Rake it in(对抗搜索)

阅读量：2135 次

发布时间：2019-04-30

本文共 1322 字，大约阅读时间需要 4 分钟。

题目大意：

Alice和Bob在玩一种名为“Rake It In”的游戏，起初有一个4*4的棋盘，每一格为一个1~10的整数，两人轮流行动，各自k次，行动者选择棋盘中某一个2*2的区域，将这四个元素求和，加到最终答案中，并将四个元素按逆时针旋转90度，Alice先行。Alice的目标是最大化最后的答案，Bob相反。请写一个程序计算，在两人都最聪明的情况下，最终答案为多少。
题解：

对抗搜索

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;const int INF=1000000007;typedef long long ll;int k;int a[10][10];int calc(int i,int j){ return a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];}void trans(int x,int y){ int t=a[x][y]; a[x][y]=a[x][y+1]; a[x][y+1]=a[x+1][y+1]; a[x+1][y+1]=a[x+1][y]; a[x+1][y]=t;}void ftrans(int x,int y){ int t=a[x][y]; a[x][y]=a[x+1][y]; a[x+1][y]=a[x+1][y+1]; a[x+1][y+1]=a[x][y+1]; a[x][y+1]=t;}int play(int t){ if(t==2*k) { int score(INF); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) score=min(score,calc(i,j)); return score; } else if(t&1) { int score(0); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { trans(i,j); score=max(score,play(t+1)+calc(i,j)); ftrans(i,j); } return score; } else { int score(INF); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { trans(i,j); score=min(score,play(t+1)+calc(i,j)); ftrans(i,j); } return score; } //当前算的我必须要用到后面的结果}int main(){ //freopen("input.txt","r",stdin); int T; cin>>T; while(T--) { cin>>k; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) cin>>a[i][j]; cout<
          
           <