Clasa a VII-a lecția 14 - 12 dec 2019

From Algopedia
Jump to navigationJump to search

Anunțuri (de la gigantul trezit)

Avertismente ultimatum

Avertisment ultimatum lui Moroșan: la prima temă neîncercată, sau încercată în glumă, îți vei pierde calificarea la IQ Academy. Ai prea multe avertismente pe parcurs, inclusiv în lecția de azi.

Temele sînt obligatorii

Reluăm problema temelor făcute la "'șto". Cei ce primesc trei avertismente la teme își vor pierde calificarea. Pe larg:

Observații:

  • La IQ Academy aveți două sau trei probleme la temă. Ele sînt meticulos alese (ce-o fi aia).
  • Cînd nu încercați măcar să rezolvați o problemă nu învățați un subiect.
  • La alte materii aveți teme la kilogram.
  • Drept care încercați să reduceți timpul alocat temelor de info, și așa mic.
  • Pare că spaima altor instructori dă rezultate.

Drept care o voi angaja și eu (spaima) în slujba mea.

Ce aveți de făcut?

  • Fiecare problemă trebuie încercată serios
  • Ea trebuie rezolvată conform cerințelor
  • Dacă există mai multe rezolvări și se cere o anume rezolvare, dați atenție acestui lucru
  • Dacă nu aveți nici cea mai mică idee despre cum se rezolvă un subpunct aveți opțiuni:
    • Citiți lecția
    • Urmăriți filmul lecției
    • Puneți întrebări pe Clubul Curioșilor
    • Întrebați-mă personal pe email
  • Nu este OK să stați cuminți dacă habar nu aveți cum se rezolvă un subpunct al unei probleme

Următorii elevi au avertismente legate de teme, de la începutul anului școlar:

Prima grupă:

  • Aizic lecția 3, 13
  • Benescu lecția 13
  • Burac lecția 3
  • Chivu lecțiile 3, 10, 14
  • Cojocariu: ultimatum la teme în lecția 3, 14
  • Dobre lecția 3
  • Hossu lecția 3
  • Mocanu 13
  • Musat lecția 3, 14
  • Nicola lecția 6, 14
  • Ștefănescu lecția 13

A doua grupă:

  • Cadîr lecția 6, 13, 14
  • Grecu lecția 3, 14
  • Ipate lecția 13
  • Moroșan nenumărate avertismente, inclusiv în această lecție
  • Petrescu 14
  • Stancu lecția 5, 14

La acestea se adaugă avertismentele de azi.

Știți ce sînt spaima și groaza?

Cei doi sateliți ai planetei Marte! Suntem celestiali!

Forma codului

Eu nu sînt compilator. A lăsa avertismente grave de compilare la clasa a șaptea nu este OK la IQ Academy (pe lîngă faptul că este dezgustător). Indentarea greșită asemenea. Programarea nestructurată (return în mijlocul funcțiilor) este de neacceptat. Voi aplica aceeași regulă: trei avertismente de compilare grave, sau de indentare, sau de programare nestructurată vă vor pierde selecția la IQ Academy.

Ce aveți de făcut?

  • Corectați avertismentele de compilare în CodeBlocks. Mă refer la cele periculoase, variabile neinițializate, citire cu %d în loc de %lld, etc.
  • Dacă totuși aveți avertisment în borderoul de evaluare varena, măcar atunci corectați sursa și retrimiteți.
  • Ultima sursă trimisă la temă trebuie să nu aibă avertismente grave.
  • Indentați corect.
  • Folosiți instrucțiunea return doar ca ultima instrucțiune din funcție, înainte de acolada finală (cu excepțiile menționate în lecție, citiți-le!)

Următorii elevi au avertismente grave de compilare, de la începutul anului școlar, în diverse lecții:

Prima grupă

  • Ștefanescu 13

A doua grupă

  • Dimulescu 7, 13
  • Fares 13
  • Grecu 10
  • Marcu 7, 10, 13
  • Nicu 13
  • Petrescu 10
  • Popescu 10
  • Teodorescu 10

Următorii elevi au folosit return în mijlocul funcției, de la începutul anului școlar:

Prima grupă

  • Aizic 7
  • Chivu 7
  • Cojocariu 7
  • Dobre 7
  • Iordache 7

A doua grupă

  • Fares 13
  • Grecu 10
  • Marcu 13
  • Petrescu 10
  • Voicu M 11

Concluzii

Dacă numele vostru apare cam prea des în listele de mai sus înseamnă că trebuie să luați măsuri urgente. ALtfel vă veți trezi cu ultimatum.

Tema - rezolvări

Nnr (n numere)

Problema nnr (n numere) cere implementarea exemplului 1 din lecția trecută. Ea este descrisă în lecție.

Comentarii generale

  • Problema este banală
  • Cu toate acestea majoritatea nu sînteți capabili să scrieți cod elementar.
  • Problema spunea să vă imaginați că scrieți o funcție care primește un vector. Mulți dintre voi ați făcut teste la citire, de comparație a elementelor cu n. Toată ideea era să vedem cum putem prelucra un vector necunoscut, nu unul triat la citire.

Comentarii individuale

Prima grupă

  • Aizic: idee bună, cod încîlcit cu stegulețe.
  • Badea: idee bună, cod ușor lungit, dar în regulă.
  • Benescu: idee bună, cod încîlcit cu stegulețe
  • Burac: cod foarte bun, bravo!
  • Calotă: return în mijlocul funcției, avertisment și zero la problemă. Cod încîlcit, mascat cu funcții.
  • Chivu: idee bună, cod încîlcit cu stegulețe.
  • Cojocariu: cod bun, bravo!
  • Dobre: ai lăsat programul nedepanat la o problemă banală. Frumos! Ideea este ciudată, nu o urmărește pe cea de la curs.
  • Hossu: cod bun, bravo!
  • Iordache: cod încîlcit, cu stegulețe și prelucrări în timpul citirii.
  • Mocanu: cod bun, bravo! Se scrie "parsing".
  • Mușat: citat: v[i] = 0; v[i] = numar();. Magistral! Nu înțelegi mecanismul funcțiilor. Codul rezonabil, ușor încîlcit, cu condiții inutile (i <= n în while-ul interior).
  • Nicola: idee bună, cod încîlcit cu stegulețe.
  • Ștefănescu: idee bună, cod cam încîlcit și cu stegulețe.
  • Togan: mi-e neclar cum funcționează un cod care testează if((k-1)<1000000). Total aiurea, e incredibil că nu îți dai seama că așa ceva nu se face.
  • Voicu: idee bună, cod încîlcit cu stegulețe (plus prelucrare la citire).

A doua grupă

  • Asgari: cod aproape bun, cu stegulețe
  • Cadîr: cod aproape perfect, dar cu stegulețe
  • Dimulescu: idee bună, cod încîlcit cu stegulețe
  • Fares: idee bună, cod încîlcit cu stegulețe
  • Ghica: cod bun, bravo!
  • Grecu: cod bun, bravo!
  • Ilie: cod bun, bravo!
  • Ipate: idee bună, cod încîlcit cu stegulețe
  • Marcu: cod bun, indentare proastă!
  • Moroșan: ideea e diferită față de curs și este greșită. În primul rînd faci prelucrări la citire. În al doilea rînd, dacă citești numere mai mari ca n nu marchezi nicăieri acest lucru, iar elementul în vector rămîne zero, deoarece nu îl atribui la numărul citit. Algoritmul este greșit grav. În plus, ai return în mijlocul funcției, avertisment și zero la problemă.
  • Nicu: atenție, pentru isdigit() trebuie să incluzi ctype.h. Indentare incorectă. Idee bună, cod încîlcit, cu stegulețe.
  • Petrescu: idee bună, cod încîlcit, cu stegulețe. Faci prelucrări în timpul citirii.
  • Popescu: idee bună, cod ineficient, care nu se oprește cînd își dă seama că nu poate fi permutare. Ca exemplu, ai o căutare de element într-un vector, chiar la final. Nu e deloc OK, te rog să te dezobișnuiești să scrii astfel de cod. Faci prelucrări în timpul citirii.
  • Rebengiuc: cod foarte bun, bravo!
  • Rughiniș: cod interesant, recursiv. Ușor ineficient, nu te oprești cînd detectezi că nu poate fi permutare.
  • Stancu: avertismente de compilare, avertisment și zero la problemă. Idee bună, codul este incorect.
  • Tatomir: idee bună, cod foarte încîlcit cu stegulețe. Încearcă să scapi de încîlceala asta, este imperativ. Ai un mod peticit de a programa. Gîndește algoritmul înainte de a te așeza la calculator. Da, cu o foaie și un creion în față.
  • Teodorescu: idee bună, cod rezonabil, ușor ineficient (repeți condiții). Ai optimizat scrierea a două caractere, dar nu citirea a milioane. Ha!
  • Voicu: idee bună, dar codul este încîlcit, cu stegulețe. În plus, așa ceva este interzis: for(i=1; i<=n && !nu; i++). Trebuia să folosești un while. Vezi regulile de programare.

Permutări1

Problema permutări1 este o problemă clasică. Ea cere, la origine, să se calculeze suma anumitor permutări specificate la intrare. Soluția cerută de problemă este una prin de generare eficientă a permutărilor, folosind liste.

De data aceasta se cere o soluție bazată pe generarea permutărilor pe baza numărului lor de ordine.

Sport

Problema Sport a fost dată la ONI 2011 clasa a 8a.

Comentarii generale

  • Avertismente celor ce nu au trimis soluție: cojocariu, mușat, nicola, cadîr, moroșan, stancu
  • Avertismente celor ce nu au încercat punctul doi al problemei: chivu, grecu, petrescu
  • Avertismente celor cu avertismente de compilare (și zero la punctajul problemei): aizic, nicu, teodorescu

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-12-12-clasa-7-lectie-info-14-720p.mp4</html5media>

Tipul coadă

Coada (în engleză queue) este o "grămadă" de obiecte ordonate după ordinea *FIFO*: first in, first out. Aceasta înseamnă că putem adăuga obiecte în coadă, iar atunci cînd le vom scoate, le vom scoate în aceeași ordine în care le-am adăugat. Ne aducem aminte că, prin contrast, stiva scoate obiectele în ordine inversă față de cum au fost adăugate (ordine *LIFO*).

Coada ca tip de date abstract

Ne aducem aminte despre ideea de tip de date abstract: un tip de date abstract este un model matematic. Acest model definește operații asupra tipului de date, precum și restricții asupra efectului acestor operații. Tipurile de date abstracte sînt utile în simplificarea algoritmilor, deaorece descompun problema în subprobleme mai mici, cunoscute și studiate.

Tipul de date abstract coadă definește operațiile:

  • enqueue, care adaugă un element la coadă
  • dequeue, care scoate un element din coadă
  • empty, care ne spune dacă coada este goală
  • full, care ne spune dacă coada este plină

Restricțiile sînt asupra ordinii de returnare a elementelor și anume ele trebuie returnate după regula "primul venit primul plecat". De aceea se spune că o coadă este o structură de tip FIFO (first in, first out).

Coada ca tip abstract de date

Implementarea cozilor cu vectori circulari

Precum am mai spus, tipurile de date abstracte separă funcționalitatea de implementare. În cazul cozii există mai multe implementări posibile. Noi vom studia una dintre cele mai folosite: implementarea cu vectori circulari. Această implementare:

  • Folosește un vector pentru a păstra elementele și doi indici, primul și ultimul care memorează poziția primului, respectiv ultimului element din coadă. Pentru a nu deplasa elemente atunci cînd scoatem un element din coadă vom incrementa doar poziția primului element. Atunci cînd adăugăm un element în coadă incrementăm poziția ultimului element.
  • Pentru a refolosi golurile rămase în urmă la scoaterea din coadă și a nu deplasa cei doi indici la infinit vom defini o mărime maximă a cozii, n. Atunci cînd unul din indici depășește această mărime el revine la zero. Logic vorbind după ultimul element din vector urmează din nou primul. De aceea spunem că vectorul este circular. Formula de actualizare a indicilor devine primul = (primul + 1) % n și ultimul = (ultimul + 1) % n, unde n este numărul maxim de elemente din coadă.
    Implementare coadă cu vector circular
  • Observăm că primul este poziția primului element din coadă, iar ultimul este poziția primului element liber din vector.
  • Coadă goală. Cum răspundem la întrebarea "este coada goală"? Se observă că acest lucru se întimplă cînd primul == ultimul.
  • Coada plină. Cum răspundem la întrebarea "este coada plină"? Observăm că aceasta se întîmplă tot atunci cînd primul == ultimul. Pentru a diferenția între aceste două cazuri vom "sacrifica" un element din vector, folosind numai n-1 poziții. În felul acesta testul de coadă plină va fi (ultimul + 1) % n == primul.

Observații:

  • În această implementare cele patru operații au complexitate O(1).
  • Important: în practică, pentru a nu face împărțiri, dimensiunea maximă a cozii va fi o putere a lui doi, constantă definită în program.
  • Unul din avantajele acestei implementări, de care veți auzi în detaliu în facultate este că scoaterea de elemente se poate face în paralel cu adăugarea, de exemplu în cazul cînd un proces generează elementele de adăugat și un alt proces, independent, colectează elementele spre procesare.

Exemple de probleme ce folosesc tipul coadă

Exemple de probleme ce folosesc cozi în rezolvări:

  • maxim2 dată la concursul ONI 2019 clasa a 6a (punctul2)
  • livada dată la cercul de informatică Vianu 2014 clasa a 9a

La pbinfo.ro:

BFS Fill (algoritmul lui Lee)

În anul 1961 C. Y. Lee a publicat un algoritm de studiu al căilor de conectare între două puncte în diagrame electronice. Algoritmul original presupune o rețea plană (un circuit electronic) în care, mulțumită proprietăților curentului electric, toate muchiile sînt de lungime unu. De-a lungul timpului (și aparent mai mult în România) acest algoritm a ajuns să fie asociat cu parcurgerea pe lățime a unei matrice, drept pentru care acesta este modul în care îl voi prezenta aici.

Deoarece algoritmul lui Lee este o parcurgere pe lățime ar trebui predat după conceptul de parcurgere pe lățime. De aceea, în această lecţie, voi încerca să prezint ambele.

Aplicații ale parcurgerii pe lățime

  • Găsirea drumului minim de la un punct la un altul, sau la mai multe puncte finale.
  • Mai puțin menționat: fill cu mai puțină memorie suplimentară (dar și mai lent)

Pentru exemplificare, să considerăm următoarea problemă: se dă un labirint codificat ca o matrice cu zero și unu, zero semnificînd loc liber și unu fiind element obstacol (zid). Se dau de asemenea un punct de start și unul de final. În matrice ne putem deplasa pe linie sau pe coloană, cu condiția să nu avem un obstacol. Să se calculeze, lungimea drumului minim între cele două puncte, dacă există un astfel de drum.

Parcurgerea în adîncime

Cînd am discutat despre algoritmul flood fill am menționat că el este o parcurgere a matricei în adîncime, deoarece traversarea elementelor matricei se face avansînd din vecin în vecin pînă ce se ajunge la o fundătură (un obstacol, ieșire din matrice, sau element deja parcurs). Am denumit această parcurgere DFS (depth first search), aceasta însemnînd că în alegerea noului element de vizitat preferăm adîncimea. Ne putem imagina această parcurgere cu un fir subțire de apă care curge într-o direcție oarecare, apoi, cînd nu mai poate schimbă direcția. Cînd ramura curentă se "înfundă" apa se va ramifica din firul principal undeva cel mai aproape de fundătură, acolo unde o poate lua pe altă direcție.

Am menționat atunci că pentru acest tip de parcurgere avem nevoie de o stivă pentru memorarea elementelor ce urmează a fi parcurse. Stiva este fie explicită (nu am vorbit despre aceasta), fie implicită, într-o implementare recursivă. Această stivă are consecințe: ea adaugă O(MxN) memorie suplimentară.

Folosind parcurgerea în adîncime, flood fill, putem răspunde la întrebarea dacă există drum între cele două puncte, dar nu putem calcula drumul minim.

Parcurgerea pe lățime

Prin contrast, ne putem imagina o parcurgere pe lățime. În această parcurgere vom traversa mai întîi elementele vecine cu elementul de start. Apoi vom continua cu elementele vecine cu ele. Și apoi cu elementele vecine cu vecinele, și așa mai departe. Putem vizualiza această parcurgere dacă ne imaginăm că turnăm apă în punctul de pornire. Ea se va împrăștia uniform în toate direcțiile. Dacă va da de obstacole ea va merge de-a lungul lor și le va ocoli. La orice moment distanța între orice punct de pe frontiera apei și punctul de start este aceeași.

Denumim această parcurgere BFS (breadth first search), deoarece în alegerea noului element de parcurs vom prefera lățimea. La fiecare iterație k vom trata elementele aflate la distanță k de punctul original. Ele formează frontiera (marginea) apei, în exemplul nostru. După fiecare iterație frontiera va fi înlocuită cu o nouă frontieră aflată la distanță mai mare cu unu decît vechea frontieră.

Precum vom vedea mai jos această parcurgere este similară cu cea în adîncime, diferența fiind că ea folosește o coadă în loc de stivă pentru memorarea elementelor ce urmează a fi parcurse. Spre deosebire de flood fill, coada trebuie să fie explicită. De aceea algoritmul poate părea foarte diferit de flood fill, dar, în realitate nu este.

Exemplificare grafică

Să vedem niște vizualizări ale algoritmului BFS fill preluate de la wikipedia: algoritm flood fill:

Exemplu de BFS fill cu 4 direcții

Implementarea parcurgerii pe lățime în matrice

Cum implementăm parcurgerea pe lățime? Cum memorăm frontiera? O idee imediată ar fi să ținem două frontiere: cea curentă, în curs de procesare, și cea nouă, în curs de generare. La fiecare iterație calculăm o nouă frontieră pe baza celei din-nainte. Apoi comutăm pe frontiera cea nouă. Ce conțin frontierele (ce stocăm)? Vom păstra identificatorii unici ai elementelor matricei, respectiv linia și coloana. Frontierele vor fi vectori de perechi (linie, coloană). Această metodă funcționează, dar nu este nici cea mai simplă și nici cea mai economică ca memorie.

În practică nu vom face distincția între frontiera veche și cea nouă. Elementele din frontiera nouă vor fi adăugate la frontiera veche, la sfîrșit. Vom avea astfel o singură frontieră de elemente de procesat. Vom procesa elementele de la începutul frontierei și vom adăuga elementele noi, vecinii, la finalul frontierei. În imaginea noastră cu apa punctele procesate vor descrie o spirală în jurul punctului de pornire.

În acest fel ajungem la structura de date pe care o vom folosi pentru stocarea punctelor de frontieră: coada. Așa cum am menționat mai sus, în loc de stivă vom folosi o coadă de perechi (linie, coloană) pentru stocarea elementelor ce urmează a fi parcurse. La un pas vom extrage din coadă primul element și vom adăuga elementele vecine lui la finalul cozii, cîtă vreme ele nu se află deja în coadă (coada conține numai elemente unice).

Algoritmul de parcurgere BFS

Iată o schiță de algoritm, care nu este neapărat universal valabil, dar poate fi adaptat diverselor situații. Această versiune de algoritm își propune să găsească cel mai scurt drum de la (lstart, cstart) la (lend, cend):

  1. Inițializează matricea labirint L[][] cu 0 pentru loc liber și -1 pentru obstacol
  2. Inițializează coada cu elementul de pornire (lstart, cstart)
  3. Setează L[lstart][cstart] <- 1 // distanța inițială
  4. Execută:
    1. Scoate primul element din coadă. Fie el linia (lin, col)
    2. Setează dist <- L[lin][col] // distanța acestui element
    3. Pentru fiecare vecin (l, c) al lui (lin, col)
      1. Dacă L[l][c] = 0 // nu se află în coadă și nici nu este obstacol
        1. Adaugă (l, c) în coadă
        2. Setează L[l][c] <- dist + 1
  5. Cîtă vreme coada nu este vidă și (lin, col) nu este destinația (lend, cend)
  6. Afișează L[lin][col] // distanța pînă la cel mai apropiat punct destinație

Note de implementare

  • Vecinii unui element din matrice pot fi fie cei adiacenți pe linie și coloană, fie și cei pe diagonală, algoritmul funcționează la fel.
  • De obicei vom folosi tehnicile invățate:
    • Bordarea matricelor pentru a scăpa de testul de ieșire din matrice
    • Vectorii de direcție pentru a genera ușor vecinii
  • Problema poate fi considerată una de simulare: simulăm parcurgerea tuturor traseelor optime în același timp.
  • Dacă nu există drum între cele două puncte algoritmul se va termina cînd coada devine goală.
  • În funcție de ceea ce se cere (drum minim pînă la destinație, drum minim pînă la anumite puncte, sau drum minim pînă la toate elementele matricei) coada poate fi parcursă pînă la final, sau ne putem opri cînd anumite condiții ale simulării au fost îndeplinite, cum ar fi atingerea punctului destinație.
  • Cum știm dacă un element se află deja în coadă? Printr-o matrice de frecvență: la momentul adăugării în coadă vom marca aceasta în matrice. De cele mai multe ori putem combina matricea de frecvență cu matricea de distanțe (ca în algoritmul de mai sus): un element diferit de zero semnifică distanța acelui element la punctul de start. În această notație obstacolele trebuie memorate ca numere negative pentru a nu fi confundate cu distanțe.
  • Cum știm că am ajuns în punctul final? Putem să testăm explicit linia și coloana. Dar dacă avem mai multe puncte finale trebuie să le marcăm într-o matrice. Această matrice se poate de obicei combina cu matricea de frecvență și cu cea de distanțe, deoarece avem nevoie doar de un bit unu sau zero.
  • Algoritmul poate fi adaptat să calculeze drumul minim de la mai multe puncte de pornire la mai multe puncte destinație. În acest caz vom inițializa coada cu toate punctele de pornire.

Reconstrucția drumului minim

Pentru a reconstitui un drum minim între sursă și destinație vom porni invers: de la destinație și vom avansa în L[][] pe elemente descrescătoare din unu în unu, pînă ce ajungem la sursă. Atenție, drumul nu este neapărat unic.

Implementarea cozii de coordonate

Pentru coadă vom folosi un vector circular de mărime 2(M+N) (vezi explicația la capitolul de complexități). Vom avea o variabilă, prim care păstrează indicele de adăugare în coadă, precum și o variabilă ultim care păstrează poziția primului element "gol", în afara cozii. Acești doi indici vor avansa circular, modulo mărimea cozii.

Coada poate să fie un vector de elemente tip struct, sau doi vectori separați. Prima variantă este mai bună din punct de vedere cache, dar poate duce la risipă de memorie în anumite situații, dacă elementul de tip struct nu ocupă un număr de octeți divizibil cu patru (sau cu lungimea cuvîntului de memorie).

Vom folosi trei funcții:

  • enqueue( lin, col ) care adaugă elementul (lin, col) în coadă
  • dequeue() care extrage elementul (lin, col) din coadă
  • emptyqueue() care returnează 1 dacă coada este vidă

Iată o posibilă implementare ce presupune că numărul de linii și coloane este maxim 255:

int prim, ultim;
unsigned char coadal[NCOADA], coadac[NCOADA]; // coordonate mici

// adauga coordonate in coada
static inline void enqueue( int l, int c ) {
  coadal[ultim] = l;
  coadac[ultim] = c;
  ultim = (ultim + 1) % NCOADA;
}

// scoate coordonate din coada
static inline int dequeue() {
  int retval = coadal[prim] * 256 + coadac[prim];

  prim = (prim + 1) % NCOADA;

  return retval;
}

// returneaza 1 cind coada este goala
static inline int emptyqueue() {
  return prim == ultim;
}

Observații:

  • Funcția dequeue() returnează două valori, linie și coloană. Ele fiind mici le-am combinat într-un singur întreg. Acest lucru este posibil în general, deoarece putem combina două valori unsigned short într-un unsigned int, ceea ce ne permite linii și coloane pînă în 65535, număr în general acoperitor pentru o matrice stocată în memorie.
  • Astfel am putea să stocăm în coadă direct produsul returnat de funcția dequeue(). Avantajele se datorează, în mare, cache-ului.

Complexități în timp și spațiu

Timpul de execuție este O(MxN) deoarece fiecare element al matricei va fi luat în calcul cel mult o dată.

Memoria necesară este O(MxN) deoarece avem nevoie de matricea de distanțe, matricea de frecvențe și cea de puncte terminale, precum și memoria ocupată de coadă. În realitate, de cele mai multe ori putem unifica matricele suplimentare, unindu-le cu matricea labirint. În acest caz memoria suplimentară este cea a cozii. La momentul cînd scriu aceste rînduri nu am găsit o estimare asupra dimensiunii maxime a cozii necesare. Intuitiv ea este O(M+N), deoarece frontiera, într-un labirint fără obstacole, cînd punctul de pornire este în mijloc, nu va depăși M+N. Este neclar dacă o altă matrice și un alt punct de pornire o poate face să depășească M+N și cu cît. Ca practică de implementare sfatul meu este să o dimensionați de 2(M+N), acoperitor, deoarece este un număr oricum mult mai mic decît matricea deja stocată, MxN.

Datorită consumului atît de mic de memorie suplimentară, algoritmul lui Lee poate fi folosit ca și ca algoritm de fill pe matrice mari, sau cînd memoria suplimentară este mică. El va fi însă mai lent decît flood fill, de obicei de multe ori (20-30 de ori), ceea ce dovedește încă o dată că, pentru unii algoritmi, memoria suplimentară se traduce în timp de execuție mai mic.

Aplicații

Algoritmul lui Lee este necesar când dorim să aflăm informații despre drumuri și distanțe:

  • Găsirea ieșirii dintr-un labirint / castel / hartă.
  • Găsirea celui mai scurt drum între două puncte dintr-o matrice.
  • În lumea reală, proiectarea de circuite electronice

Exemple de probleme ce folosesc algoritmul lui Lee

Orice problemă rezolvabilă prin flood fill este, desigur, rezolvabilă și cu Lee, folosind mai puțină memorie, dar consumînd mai mult timp pentru executarea programului. N-am găsit foarte multe exemple de probleme ce necesită Lee, dar nu se pot rezolva cu flood fill. Iată cîteva exemple:

Exemple de probleme ce folosesc algoritmul lui Lee în rezolvări:

La varena.ro:

  • alee dată la OJI 2007 clasa a 10a
  • insule dată la OJI 2009 clasa a 10a
  • miting dată la OJI 2016 clasa a 10a (grea)

La infoarena.ro:

Temă

Alte teme interesante

  • fractii3 pentru coadă. Enunțul are anumite neclarități:
    • Șirurile de fracții nu vor depăși k, deci nu trebuie să ne îngrijorăm ce se întîmplă dacă avem mai mult de k fracții într-un șir.
    • Numerele a și b din perechile citite par a depăși limita de 10000, promisă în enunț. Atenție, deci, la compararea fracțiilor, înmulțirile s-ar putea să trebuiască făcute pe long long.
  • Problemele menționate mai sus cu cozi sau Lee

Rezolvări aici [2]