设$f0[i][j][x][y][S]$表示盗贼位于$(i,j)$，守卫位于$(x,y)$，每棵苹果树苹果数量为$S$，盗贼先手时盗贼还能偷多少苹果。

设$f1[i][j][x][y][S]$表示盗贼位于$(i,j)$，守卫位于$(x,y)$，每棵苹果树苹果数量为$S$，守卫先手时盗贼还能偷多少苹果。

转移：$f0$为后继$f1$状态的最大值，$f1$为后继$f0$状态的最小值。

假设所有状态的值都是$0$，将所有状态加入队列依次进行松弛，发现值改变则继续入队列。

因为每个状态的值只有$13$种取值，所以最多入队列$13$次。

 

#include
     
      const int N=230500,M=1048575;char a[9][9];int Case,n,m,ca,cnt,i,j,k,x,y,nx,ny,S,sx,sy,tx,ty,o,tmp,flag;int id[7][8][7][8][256],apple[7][8];int f0[N],f1[N];bool in0[N],in1[N];int head,tail,q[M+5];bool can[7][8];int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};int g0[N][12],g1[N][12],h0[N][12],h1[N][12];inline int get(int x,int y){return x>>(y<<1)&3;}inline int down(int x,int y){return x-(1<<(y<<1));}inline void umin(int&a,int b){a>b?(a=b):0;}inline void umax(int&a,int b){a
      
       >1]+(u&1));  }  if(now!=old){    f0[x]=now;    if(!in0[x])q[tail=(tail+1)&M]=x,in0[x]=1;  }}inline void cal1(int x){  int old=f1[x],now=12;  for(int i=1;;i++){    int u=g1[x][i];    if(!u)break;    umin(now,f0[u]);  }  if(now!=old){    f1[x]=now;    if(!in1[x])q[tail=(tail+1)&M]=-x,in1[x]=1;  }}int main(){  n=5,m=6;  scanf("%d",&Case);  while(Case--){    for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)can[i][j]=0,apple[i][j]=-1;    ca=0;    for(i=1;i<=n;i++){      scanf("%s",a[i]+1);      for(j=1;j<=m;j++){        if(a[i][j]!='#')can[i][j]=1;        if(a[i][j]=='3')apple[i][j]=ca++;        if(a[i][j]=='S')sx=i,sy=j;        if(a[i][j]=='T')tx=i,ty=j;      }    }    cnt=0;    for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)for(x=0;x<=n+1;x++)for(y=0;y<=m+1;y++)for(S=0;S<256;S++)id[i][j][x][y][S]=0;    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(can[i][j])      for(x=1;x<=n;x++)for(y=1;y<=m;y++)if(can[x][y]&&((x!=i)||(y!=j)))        for(S=0;S<256;S++)id[i][j][x][y][S]=++cnt;    for(i=0;i<=cnt;i++){      f0[i]=f1[i]=0;      g0[i][0]=g1[i][0]=h0[i][0]=h1[i][0]=0;    }    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(can[i][j])      for(x=1;x<=n;x++)for(y=1;y<=m;y++)if(can[x][y]&&((x!=i)||(y!=j)))        for(S=0;S<256;S++){          o=id[i][j][x][y][S];                    flag=0;          tmp=apple[i][j];          if(~tmp){            if(get(S,tmp))add01(o,id[i][j][x][y][down(S,tmp)],1);            else add01(o,o,0);          }          for(k=0;k<4;k++){            nx=i+dx[k],ny=j+dy[k];            if(!can[nx][ny]||(nx==x&&ny==y))continue;            flag=1;            tmp=apple[nx][ny];            if(~tmp){              if(get(S,tmp))add01(o,id[nx][ny][x][y][down(S,tmp)],1);              else add01(o,id[nx][ny][x][y][S],0);            }else add01(o,id[nx][ny][x][y][S],0);          }          if(!flag)add01(o,o,0);                    flag=0;          tmp=apple[x][y];          if(~tmp){            if(get(S,tmp))add10(o,id[i][j][x][y][down(S,tmp)]);            else add10(o,o);          }          for(k=0;k<4;k++){            nx=x+dx[k],ny=y+dy[k];            if(!can[nx][ny]||(nx==i&&ny==j))continue;            flag=1;            tmp=apple[nx][ny];            if(~tmp){              if(get(S,tmp))add10(o,id[i][j][nx][ny][down(S,tmp)]);              else add10(o,id[i][j][nx][ny][S]);            }else add10(o,id[i][j][nx][ny][S]);          }          if(!flag)add10(o,o);        }    for(i=1;i<=cnt;i++){      g0[i][g0[i][0]+1]=0;      g1[i][g1[i][0]+1]=0;      h0[i][h0[i][0]+1]=0;      h1[i][h1[i][0]+1]=0;    }    head=1,tail=cnt;    for(i=1;i<=cnt;i++){      in0[i]=0,in1[i]=1;      q[i]=-i;    }    while(head!=(tail+1)&M){      x=q[head];      head=(head+1)&M;      if(x>0){        in0[x]=0;        for(i=1;h0[x][i];i++)cal1(h0[x][i]);      }else{        x=-x;        in1[x]=0;        for(i=1;h1[x][i];i++)cal0(h1[x][i]);      }    }    printf("%d\n",f0[id[tx][ty][sx][sy][255]]);  }  return 0;}