De ce contează?
Cauți drumul cel mai scurt prin oraș cu mașina, dar rezervorul ține doar 10 litri și benzinăriile sunt rare. Treci de două ori prin aceeași intersecție: o dată cu rezervorul plin, o dată aproape gol. E aceeași situație? Deloc. Cu plinul făcut poți s-o tai pe bulevardul lung, fără nicio benzinărie; pe uscat ești obligat la un ocol după benzină. Aceeași poziție pe hartă — viitor complet diferit. Deci „unde sunt" nu e doar intersecția: e intersecția plus câți litri mai ai. Din clipa în care vezi asta, harta ta reală nu mai e orașul, ci un graf mai mare, în care fiecare intersecție apare de 11 ori: o dată pentru fiecare nivel al rezervorului, de la 0 la 10.
Ideea-cheie
În problemele clasice de drum minim, nodul e o poziție: o intersecție, o celulă, un oraș. Dar multe enunțuri de concurs atașează poziției o resursă sau o condiție — benzină care se consumă, chei pe care le aduni, un număr limitat de teleportări, cerința ca drumul să aibă lungime pară. Atunci poziția singură nu mai descrie situația, iar drumul minim trebuie căutat în graful stărilor.
Partea liniștitoare: nu înveți niciun algoritm nou. Graful stărilor e un graf absolut obișnuit — are noduri, muchii, eventual costuri — doar că nodurile lui sunt perechi sau triplete, nu simple poziții. BFS și Dijkstra rulează pe el neschimbate, literă cu literă.
Starea = poziția + tot ce îți schimbă viitorul. Dacă două situații cu aceeași
poziție permit mutări diferite (sau costuri diferite) de aici încolo, ele sunt
noduri DIFERITE. Nodul devine (pozitie, resursa), muchia devine o mutare validă
între stări, iar drumul minim de la starea inițială la orice stare-țintă se
calculează cu BFS sau Dijkstra standard — algoritmul nu află niciodată că nodul
lui „ascunde" o poveste.