The Floor is Lava - possibile ottimizzazione?

Algoritmi
1

Link al problema

Ho eseguito un djikstra sulla grid e mi funziona tutto correttamente. Mi domandavo pero’ se fosse possibile ottimizzare il tutto ulteriormente dato che vedo che alcuni subtask mi vanno oltri 0.100s.

long djikstra(const vector<vector<bool>>& grid) {
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    vector<vector<long>> dist(grid.size(), vector<long>(grid[0].size(), numeric_limits<long>::max()));

    dist[2][2] = 0;
    pq.emplace(2, 2);

    while(!pq.empty()) {
        ll curr_node = pq.top();
        pq.pop();

        long x = curr_node.first;
        long y = curr_node.second;

        long curr_dist = dist[x][y];

        // Vertical checks
        if(grid[x - 1][y] && dist[x - 1][y] > curr_dist + 1) {
            dist[x - 1][y] = curr_dist + 1;
            pq.emplace(x - 1, y);
        }

        if(grid[x + 1][y] && dist[x + 1][y] > curr_dist + 1) {
            dist[x + 1][y] = curr_dist + 1;
            pq.emplace(x + 1, y);
        }

        if(grid[x - 2][y] && dist[x - 2][y] > curr_dist + 1) {
            dist[x - 2][y] = curr_dist + 1;
            pq.emplace(x - 2, y);
        }

        if(grid[x + 2][y] && dist[x + 2][y] > curr_dist + 1) {
            dist[x + 2][y] = curr_dist + 1;
            pq.emplace(x + 2, y);
        }

        // Horizontal checks
        if(grid[x][y - 1] && dist[x][y - 1] > curr_dist + 1) {
            dist[x][y - 1] = curr_dist + 1;
            pq.emplace(x, y - 1);
        }

        if(grid[x][y + 1] && dist[x][y + 1] > curr_dist + 1) {
            dist[x][y + 1] = curr_dist + 1;
            pq.emplace(x, y + 1);
        }

        if(grid[x][y - 2] && dist[x][y - 2] > curr_dist + 1) {
            dist[x][y - 2] = curr_dist + 1;
            pq.emplace(x, y - 2);
        }

        if(grid[x][y + 2] && dist[x][y + 2] > curr_dist + 1) {
            dist[x][y + 2] = curr_dist + 1;
            pq.emplace(x, y + 2);
        }

        // Diagonal checks
        if(grid[x - 1][y + 1] && dist[x - 1][y + 1] > curr_dist + 1) {
            dist[x - 1][y + 1] = curr_dist + 1;
            pq.emplace(x - 1, y + 1);
        }

        if(grid[x + 1][y + 1] && dist[x + 1][y + 1] > curr_dist + 1) {
            dist[x + 1][y + 1] = curr_dist + 1;
            pq.emplace(x + 1, y + 1);
        }

        if(grid[x + 1][y - 1] && dist[x + 1][y - 1] > curr_dist + 1) {
            dist[x + 1][y - 1] = curr_dist + 1;
            pq.emplace(x + 1, y - 1);
        }

        if(grid[x - 1][y - 1] && dist[x - 1][y - 1] > curr_dist + 1) {
            dist[x - 1][y - 1] = curr_dist + 1;
            pq.emplace(x - 1, y - 1);
        }
    }

    return dist[grid.size() - 3][grid[0].size() - 3];
}

Questo e’ l’algoritmo che uso io, molto basico. C’e’ qualche ottimizzazione possibile?

2

Gli archi del grafo non sono pesati, quindi non serve dijkstra ma basta sapere che prima raggiungi un nodo, più è vicino alla sorgente. In questo modo elimini il fattore logN della std::priority_queue.
Soluzione: Basta una BFS

1 Mi Piace