Submission #391805

#	Time	Username	Problem	Language	Result	Execution time	Memory
391805		ocarima	Robots (APIO13_robots)	C++14	100 / 100	1325 ms	156824 KiB

robots

#include<bits/stdc++.h>

using namespace std;

// PES 2021 - abril.  "Bacterias alienigenas" (60 pts: DFS + Busqueda priorizada sobre estado ampliado usando multiples colas en vez de cola priorizada)

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAX_N 503
#define MAX_BACTERIA 10
#define CICLADO 1000

#define norte 0
#define este 1
#define sur 2
#define oeste 3
#define invalido 0
#define valido 1
#define rotahorario 2
#define rotaantihorario 3

#define fila first
#define columna second

#define inicio first.first
#define fin first.second
#define cfila second.first
#define ccolumna second.second

#define horario(x) ((x + 1) & 3)
#define antihorario(x) ((x + 3) & 3)
#define une(a, b, c, d) ((a << 24) | (b << 20) | (c << 10) | d)
#define binicio(x) (x >> 24)
#define bfin(x) ((x >> 20) & 0xF)
#define cfila(x) ((x >> 10) & 0x3FF)
#define ccolumna(x) (x & 0x3FF)

int n, filas, columnas, mapa[MAX_N][MAX_N], res, tmp, maximo, cnt;
int dist[MAX_BACTERIA][MAX_BACTERIA][MAX_N][MAX_N];
pii destino[4][MAX_N][MAX_N], bact[MAX_BACTERIA], delta[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, coorddest;
int actual;
string s;

pii dfs(int fil, int col, int dir){
    if (destino[dir][fil][col].fila) return destino[dir][fil][col];  // SI YA CONOCE EL RESULTADO, DEVUELVELO
    if (mapa[fil][col] == invalido) return {fil, col}; // SI ES UNA POSICION INVALIDA DEVUELVELA

    int dirorig = dir;
    if (mapa[fil][col] == rotahorario) dir = horario(dir);
    else if (mapa[fil][col] == rotaantihorario) dir = antihorario(dir);

    if (mapa[fil + delta[dir].fila][col + delta[dir].columna] == invalido) return {fil, col};

    destino[dirorig][fil][col] = {CICLADO, CICLADO};
    return destino[dirorig][fil][col] = dfs(fil + delta[dir].fila, col + delta[dir].columna, dir);
}

int main()
{
    fastio;

    cin >> n >> columnas >> filas;

    // LEE EL MAPA
    rep(fil, 1, filas){
        cin >> s;
        rep(col, 1, columnas){
            if (s[col - 1] == '.') mapa[fil][col] = valido;
            else if (s[col - 1] == 'x') mapa[fil][col] = invalido;
            else if (s[col - 1] == 'A') mapa[fil][col] = rotaantihorario;
            else if (s[col - 1] == 'C') mapa[fil][col] = rotahorario;
            else{
                mapa[fil][col] = valido;
                bact[s[col - 1] - '0'].fila = fil;
                bact[s[col - 1] - '0'].columna = col;
            }
        }
    }

    // CALCULA A DONDE LLEGA UN ROBOT QUE SEA EMPUJADO EN CADA UNA DE LAS 4 DIRECCIONES DESDE CADA PUNTO POSIBLE DE ORIGEN.
    rep(fil, 1, filas){
        rep(col, 1, columnas){
            rep(dir, norte, oeste){
                destino[dir][fil][col] = dfs(fil, col, dir);
            }
        }
    }

    // HAZ UNA BUSQUEDA USANDO UNA COLA PRIORIZADA, EL ESTADO ES LA COORDENADA MAS LA ETIQUETA DE LA BACTERIA
    // LAS TRANSICIONES SON
    // LAS 4 DIRECCIONES EN QUE SE PUEDE EMPUJAR
    // LAS ETIQUETAS CON LAS QUE SE PUEDE UNIR
    // LOS ESTADOS VALIDOS SON AQUELLOS QUE REDUZCAN EL MEJOR CAMINO ENCONTRADO
    maximo = filas * columnas + 1;
    rep(fil, 1, filas) rep(col, 1, columnas) rep(b1, 1, n) rep(b2, b1, n) dist[b1][b2][fil][col] = maximo;

    vector<vector<int> > q(maximo);

    rep(b, 1, n){
        q[0].pb(une(b, b, bact[b].fila, bact[b].columna)); // INICIALMENTE AGREGA A LA COLA TODAS LAS BACTERIAS SOLAS CON SU POSICION
        dist[b][b][bact[b].fila][bact[b].columna] = 0;
    }

    cnt = 0;
    while (cnt < maximo){
        while (q[cnt].size()){
            actual = q[cnt].back();
            q[cnt].pop_back();

            // UNICAMENTE PROCESALO SI NADIE LO HA MEJORADO
            if (dist[binicio(actual)][bfin(actual)][cfila(actual)][ccolumna(actual)] == cnt){
                // HAZ TRANSICIONES DE EMPUJAR LA BACTERIA QUE SE TIENE EN LAS 4 DIRECCIONES
                rep(dir, norte, oeste){
                    coorddest = destino[dir][cfila(actual)][ccolumna(actual)];
                    if (dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] > cnt + 1){
                        q[cnt + 1].pb(une(binicio(actual), bfin(actual), coorddest.fila, coorddest.columna));
                        dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] = cnt + 1;
                    }
                }

                // TRANSICIONES QUE UNEN BACTERIAS
                rep(b, bfin(actual) + 1, n){ // VE SI PUEDES UNIR CON BACTERIAS CON ETIQUETAS "MAYORES"
                    tmp = dist[bfin(actual) + 1][b][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
                    if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)]){
                        q[tmp + cnt].pb(une(binicio(actual), b, cfila(actual), ccolumna(actual)));
                        dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)] = tmp + cnt;
                    }
                }

                repa(b, binicio(actual) - 1, 1){ // VE SI PUEDES UNIRTE CON ETIQUETAS "MENORES"
                    tmp = dist[b][binicio(actual) - 1][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
                    if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)]){
                        q[tmp + cnt].pb(une(b, bfin(actual), cfila(actual), ccolumna(actual)));
                        dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)] = tmp + cnt;
                    }
                }
            }
        }

        q[cnt].clear(); // ES NECESARIO LIMPIAR LA COLA PARA QUE NO SE QUEDE OCUPANDO MEMORIA.

        while (cnt < maximo && !q[cnt].size()) ++cnt;
    }

    res = maximo;
    rep(fil, 1, filas)
        rep(col, 1, columnas)
            res = min(res, dist[1][n][fil][col]);

    if (res == maximo) res = -1;
    cout << res;

    return 0;
}

Compilation message (stderr)

robots.cpp:48: warning: "cfila" redefined
   48 | #define cfila(x) ((x >> 10) & 0x3FF)
      | 
robots.cpp:40: note: this is the location of the previous definition
   40 | #define cfila second.first
      | 
robots.cpp:49: warning: "ccolumna" redefined
   49 | #define ccolumna(x) (x & 0x3FF)
      | 
robots.cpp:41: note: this is the location of the previous definition
   41 | #define ccolumna second.second
      |

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40