# The Floor is Lava - possibile ottimizzazione?

**URL:** <https://forum.olinfo.it/t/the-floor-is-lava-possibile-ottimizzazione/7828>\
**Category:** Algoritmi\
**Created:** [13 Novembre 2022, 4:47pm UTC](https://forum.olinfo.it/t/the-floor-is-lava-possibile-ottimizzazione/7828 "2022-11-13T16:47:10Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![R1D3R](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e99b99/32.png) [@R1D3R](https://forum.olinfo.it/u/R1D3R)\
**Post date:** [13 Novembre 2022, 4:47pm UTC](https://forum.olinfo.it/t/the-floor-is-lava-possibile-ottimizzazione/7828/1 "2022-11-13T16:47:10Z")

</div>

[Link al problema](https://training.olinfo.it/#/task/ois_lava/statement)

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.

```auto
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?

---

<div class="post-metadata">

**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\
**Post date:** [13 Novembre 2022, 5:28pm UTC](https://forum.olinfo.it/t/the-floor-is-lava-possibile-ottimizzazione/7828/2 "2022-11-13T17:28:27Z")

</div>

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