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 aprendí a resolverlos con la técnica de MINIMAX, me tope con que como podía hacer un MINIMAX sobre este problema si puede haber ciclos, ya que el MINIMAX se resuelve con una dinámica y una dinámica 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 envía el mensaje “You are trapped in the Matrix.”, y para evitar los ciclos enviamos en la dinámica 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 dinámica es 0 , indica que no lo pueden atrapar pero tampoco pudo escapar, si es -1 entonces lo atraparon, y si es 1 puede escapar. aquí les dejo el código.

/* Autor: Rodrigo Burgos Dominguez */

# include <stdio.h>
# include <string.h>

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;
}
//</string.h></stdio.h>

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

Fuente http://algorithmmx.blogspot.mx/2012/03/10358-matrix-minimax.html