Semafoare

Pentru a rezolva problema, ne vom propune să calculăm D[i][j][k] = timpul minim necesar pentru a ajunge la semaforul din intersecţia (i, j) venind din direcţia k, unde k ia valori în mulţimea {0, 1, 2, 3} ce reprezintă codificări pentru cele 4 direcţii posibile: nord, est, sud si vest. Dacă în problemă nu ar interveni semafoarele, matricea D ar putea fi calculată cu uşurinţă folosind o parcurgere in lăţime sau, mai popular, un Lee. Totuşi, se observă că o maşină nu poate aştepta mai mult de 3 minute la un semafor, deci costul pentru a ajunge în oricare din celulele adiacente poate fi cel mult 4. De aceea, vom folosi 5 cozi în parcurgerea noastră: una pentru costul curent, una pentru costul curent + 1, ... şi una pentru costul curent + 4. Observaţia făcută mai devreme ne asigură că la pasul curent vom avea triplete (i, j, k) al căror cost să depăşească costul curent+4, în afară de cele al căror cost este infinit (nu ştim nimc de distanţa minimă până la ele). Vom parcurge coada corespunzătoare costului curent şi vom proceda exact ca în cazul unei parcurgeri în lăţime. Când terminăm de parcurs coada curentă, vom muta coada de cost curent + 1 în locul celei curente, cea de cost curent + 2 în locul celei de cost curent + 1, ..., iar ultima coadă va fi vidă. Este necesar ca pentru a calcula costurile de deplasare în celulele adiacente să ştim să determinăm timpul minim în care putem intra într-o intersecţie oarecare dacă ştim că am ajuns la semaforul respectiv la momentul de timp t, venind din direcţia d1, iar pentru în această intersecţie în minutul 0 intră maşinile din direcţia d2. Timpul minim căutat se poate obţine în complexitate O(1) cu ajutorul următoarei formule: (d1 - d2 - (t%4) + 8) % 4 sau în varianta optimizată folosind operaţii pe biţi: (d1 - d2 - (t&3) + 8) & 3. Algoritmul prezentat procesează fiecare triplet (i, j, k) de un număr constant de ori, ceea ce conduce la o complexitate totală O(N*M). Acest algoritm mai poate fi aplicat în mai multe probleme precum Pădure şi Car.