/* 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
No hay comentarios:
Publicar un comentario