Descripción del problema

Se nos presenta un problema de cooperación entre dos jugadores en un laberinto representado por una cuadrícula de n×m. Cada casilla puede ser terreno libre (.), trampa (#) o portal de salida (@). Ambos jugadores comienzan en la misma posición y deben moverse simultáneamente en direcciones opuestas. Si uno de ellos alcanza un portal, puede salir del laberinto y el otro jugador queda libre para moverse en cualquier dirección.

El objetivo es determinar si existe una secuencia de movimientos tal que ambos jugadores logren escapar de la isla, y en caso afirmativo, calcular el número mínimo de movimientos necesarios. Si no es posible, devolver -1.

Entrada

La entrada consiste en:

• Una primera línea con cuatro enteros: n, m, fila_inicial, columna_inicial (1≤n,m≤2000).
• n líneas siguientes, cada una con una cadena de m caracteres representando la cuadrícula.

Ejemplo 1

Entrada:

3 3 2 2
@.@
#..
@.@

Salida: 2

Explicación: Un jugador puede ir hacia arriba y luego hacia la izquierda para alcanzar el portal (1,1). El otro jugador va hacia abajo y luego hacia la derecha para alcanzar el portal (3,3).

Solución

Para resolver este problema, podemos descomponerlo en dos fases:

1. Fase en pareja: Calculamos la distancia desde la posición inicial hasta todos los estados posibles mientras ambos jugadores se mueven en direcciones opuestas.
2. Fase individual: Calculamos la distancia desde cualquier casilla hasta el portal más cercano para cuando un jugador ya haya salido.

La solución se encuentra combinando ambas fases: para cada estado alcanzado en la fase en pareja donde al menos uno de los jguadores esté en un portal, sumamos los pasos de la fase individual necesarios para que el otro jugador alcence su portal.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const int MAX_FILAS = 2000;
const int MAX_COLS = 2000;
const int INFINITO = 1000000000;

// Estructura para representar una posición en la cuadrícula
struct Posicion {
    int f, c;
    Posicion(int fila, int col) : f(fila), c(col) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int filas, cols, f_inicio, c_inicio;
    cin >> filas >> cols >> f_inicio >> c_inicio;
    
    // Convertimos a índices base 0
    f_inicio--; c_inicio--;

    vector<string> mapa(filas);
    for (int i = 0; i < filas; i++) {
        cin >> mapa[i];
    }

    // Calculamos distancias para la fase individual (de cada casilla al portal más cercano)
    vector<vector<int>> dist_individual(filas, vector<int>(cols, -1));
    queue<Posicion> cola_individual;

    // Inicializamos con todos los portales como fuentes múltiples
    for (int i = 0; i < filas; i++) {
        for (int j = 0; j < cols; j++) {
            if (mapa[i][j] == '@') {
                dist_individual[i][j] = 0;
                cola_individual.push(Posicion(i, j));
            }
        }
    }

    // Direcciones: arriba, abajo, izquierda, derecha
    int df[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // BFS para fase individual
    while (!cola_individual.empty()) {
        Posicion actual = cola_individual.front();
        cola_individual.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nueva_f = actual.f + df[dir];
            int nueva_c = actual.c + dc[dir];
            
            if (nueva_f >= 0 && nueva_f < filas && 
                nueva_c >= 0 && nueva_c < cols &&
                mapa[nueva_f][nueva_c] != '#' && 
                dist_individual[nueva_f][nueva_c] == -1) {
                
                dist_individual[nueva_f][nueva_c] = dist_individual[actual.f][actual.c] + 1;
                cola_individual.push(Posicion(nueva_f, nueva_c));
            }
        }
    }

    // Calculamos distancias para la fase en pareja
    vector<vector<int>> dist_pareja(filas, vector<int>(cols, -1));
    queue<Posicion> cola_pareja;
    
    dist_pareja[f_inicio][c_inicio] = 0;
    cola_pareja.push(Posicion(f_inicio, c_inicio));

    // BFS para fase en pareja
    while (!cola_pareja.empty()) {
        Posicion jugador1 = cola_pareja.front();
        cola_pareja.pop();
        
        // Calculamos posición del segundo jugador (reflejo simétrico)
        int f2 = 2 * f_inicio - jugador1.f;
        int c2 = 2 * c_inicio - jugador1.c;

        for (int dir = 0; dir < 4; dir++) {
            // Movimiento del primer jugador
            int nf1 = jugador1.f + df[dir];
            int nc1 = jugador1.c + dc[dir];
            
            // Movimiento opuesto del segundo jugador
            int nf2 = f2 - df[dir];
            int nc2 = c2 - dc[dir];

            // Verificamos límites y que no sean trampas
            if (nf1 >= 0 && nf1 < filas && nc1 >= 0 && nc1 < cols &&
                nf2 >= 0 && nf2 < filas && nc2 >= 0 && nc2 < cols &&
                mapa[nf1][nc1] != '#' && mapa[nf2][nc2] != '#' &&
                dist_pareja[nf1][nc1] == -1) {
                
                dist_pareja[nf1][nc1] = dist_pareja[jugador1.f][jugador1.c] + 1;
                cola_pareja.push(Posicion(nf1, nc1));
            }
        }
    }

    // Buscamos la solución óptima combinando ambas fases
    int resultado = -1;

    for (int f = 0; f < filas; f++) {
        for (int c = 0; c < cols; c++) {
            if (dist_pareja[f][c] == -1) continue;
            
            int f_reflejo = 2 * f_inicio - f;
            int c_reflejo = 2 * c_inicio - c;
            
            // Caso 1: Primer jugador en portal
            if (mapa[f][c] == '@' && dist_individual[f_reflejo][c_reflejo] != -1) {
                int total_pasos = dist_pareja[f][c] + dist_individual[f_reflejo][c_reflejo];
                if (resultado == -1 || total_pasos < resultado) {
                    resultado = total_pasos;
                }
            }
            
            // Caso 2: Segundo jugador en portal
            if (mapa[f_reflejo][c_reflejo] == '@' && dist_individual[f][c] != -1) {
                int total_pasos = dist_pareja[f][c] + dist_individual[f][c];
                if (resultado == -1 || total_pasos < resultado) {
                    resultado = total_pasos;
                }
            }
        }
    }

    cout << resultado << endl;

    return 0;
}