teleportor

Algoritmul, pas cu pas

Reducerea la treceri între valori consecutive

Áles vizitează camerele în ordinea valorilor: întâi toate cele cu $1$, apoi cele cu $2$, etc. Între camerele cu aceeași valoare se deplasează gratis prin tunele, deci le poate vizita pe toate fără cost. Singura problemă e trecerea de la valoarea $v$ la $v+1$.

Când e nevoie de teleportor pentru $v \to v+1$? Din clasa $v$ poate ajunge gratis la orice cameră de valoare $v$. De acolo poate folosi o ușă doar dacă vreo cameră de valoare $v$ e vecină cu o cameră de valoare $v+1$. Deci:

Trecerea $v \to v+1$ cere o teleportare exact când nu există nicio pereche de camere vecine cu valorile $v$ și $v+1$.

Numărul minim de teleportări = câte valori $v \in \{1, \dots, K-1\}$ nu au nicio astfel de pereche vecină.

Menținerea sub schimbări

Ținem $adj[t]$ = numărul de muchii ale grilei ale căror capete au valorile $t$ și $t+1$. Răspunsul e numărul de $t \in [1, K-1]$ cu $adj[t] = 0$; menținem un contor teleportari al acestora.

La o schimbare a camerei $(i,j)$ din valoarea veche $o$ în $c$, doar cele $\le 4$ muchii incidente se modifică. Pentru fiecare vecin cu valoarea $w$:

• scoatem perechea veche $(o, w)$: dacă $|o-w| = 1$, $adj[\min(o,w)]$ scade (dacă ajunge la $0$, teleportari crește);
• adăugăm perechea nouă $(c, w)$: dacă $|c-w| = 1$, $adj[\min(c,w)]$ crește (dacă era $0$, teleportari scade).