10358 Matrix ( MINIMAX )

http://uva.onlinejudge.org/external/103/10358.html Estaba revisando este problema y recordando cuando intente resolverlo hace ya mas de 8 años no tenia ni idea de como resolver un problema de este tipo, cuando aprendi a resolverlos con la tecnica de minimax, me tope con que como podia hacer un minimax sobre este problema si puede haber ciclos, ya que el minimax se resuelve con una dinamica y una dinamica para poder resolver el problema no debe tener ciclos, ahora que lo vuelvo a leer, es obvio que cuando se hacen mas de 32 movimientos entonces ya no lo pueden atrapar y por tanto se envia el mensaje "You are trapped in the Matrix.", y para evitar los ciclos enviamos en la dinamica el nivel, este nivel es el numero de pasos, si es par entonces se mueve neo en otro caso se mueven los agentes, los agentes tratan de minimizar y neo trata de maximizar. Al final si el valor que regresa la dinamica es 0 , indica que no lo pueden atrapar pero tampoco pudo escapar, si es -1 entonces lo atraparon, y si es 1 puede escapar. aqui les dejo el codigo.

/* Autor: Rodrigo Burgos Dominguez */

# include 
# include 

char map[10][10];

int dx[5]={0, 1, -1, 0, 0};
int dy[5]={0, 0, 0, 1, -1};

int din[40][8][8][8][8][8][8];
int vis[40][8][8][8][8][8][8], cases;

int max(int a, int b ){ return a > b ? a : b; }
int min(int a, int b ){ return a < b ? a : b; }

void find( int a, int b, int *A,int *B, char ch ){
  int cont = 0;
  for( ; a < 8; a++, cont++)
  for(b = ( cont == 0 ) ? b : 0 ; b < 8 ; b++, cont++)
    if( map[a][b] == ch ){
      *A = a; 
      *B = b;
      return;
    }
}

int canWalk(int ax, int ay, int aX, int aY, int nx, int ny){
  if( ax < 0 || ay < 0 || nx < 0 || ny < 0 || aX < 0 || aY < 0 ) return 0;
  if( ax >= 8 || ay >= 8 || nx >= 8 || ny >= 8 || aX >= 8 || aY >= 8 ) return 0;
  if( map[ax][ay] == '#' || map[aX][aY] == '#' || map[nx][ny] == '#') return 0;
  return 1;
}

int solve( int level, int ax, int ay, int aX, int aY, int nx, int ny){
  int res, d1, d2;
  if( level >= 40 ) return 0;
  if( ax == nx && ay == ny ) return -1;
  if( aX == nx && aY == ny ) return -1;
  if( map[nx][ny] == 'P' ) return 1;
  
  if( vis[level][ax][ay][aX][aY][nx][ny] == cases) return din[level][ax][ay][aX][aY][nx][ny];
  vis[level][ax][ay][aX][aY][nx][ny] = cases;
  if( level % 2 == 0 ){ /* Move neo */
    res = -1;
    for(d1 = 0; d1 < 5; d1++) 
      if( canWalk( ax, ay, aX, aY, nx + dx[ d1 ], ny + dy[ d1 ])){
       res = max( res, solve(level + 1, ax, ay, aX, aY, nx + dx[ d1 ] , ny + dy[ d1 ]) );
      }
  }else{  /* move agents */
   res = 1;
   for( d1 = 0; d1 < 5; d1++)
   for( d2 = 0; d2 < 5; d2++)
     if( canWalk( ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny ) ){
       res = min( res, solve( level + 1, ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny) ) ;
     }
  }
  return din[level][ax][ay][aX][aY][nx][ny] = res;
}

main(){
  int ncases, ax,ay,aX,aY,nx,ny, x, r;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   for( x = 0; x < 8; x++) scanf("%s", map[ x ]);
   find( 0, 0 , &ax, &ay, 'A');
   find( ax, ay+1 , &aX, &aY, 'A');
   find( 0, 0 , &nx, &ny, 'M');
   r = solve(0, ax, ay, aX, aY, nx, ny);
   if( r == 0 ) printf("You are trapped in the Matrix.\n");
   else if( r < 0 ) printf("You are eliminated.\n");
   else printf("You can escape.\n");
  }
  return 0;
}
//

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com