Problema TAXE

[•niovan]

Buna, ma numesc Alex si am mare nevoie de ajutorul vostru  .Dupa lungi cautari(degeaba  ) pe net pt o metoda care sa ma ajute la rezolvarea problemei urmatoare am inceput incet, incet sa renunt. V-as fi foarte recunoscator daca m-ati putea ajuta cu ceva sfaturi/opinii/pareri/puncte de start/idei/etc. 
Problema suna cam asa:

Taxe
Într-o þarã în care corupþia este în floare ºi economia la pãmânt, pentru a obþine toate aprobãrile necesare în
scopul demarãrii unei afaceri, investitorul trebuie sã treacã prin mai multe camere ale unei clãdiri în care se aflã birouri.
Clãdirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pãtratic de dimensiune
n × n. Pentru a facilita accesul în birouri, toate camerele vecine au uºi între ele. În fiecare birou se aflã
un funcþionar care pretinde o taxã de trecere prin camerã (taxã care poate fi, pentru unele camere, egalã cu 0).
Investitorul intrã încrezãtor prin colþul din stânga-sus al clãdirii (cum se vede de sus planul clãdirii) ºi dore
ºte sã ajungã în colþul opus al clãdirii, unde este ieºirea, plãtind o taxã totalã cât mai micã. ªtiind cã el are în buzunar S euro ºi cã fiecare funcþionar îi pretinde taxa imediat ce investitorul intrã în birou, se cere sã se determine dacã el
poate primi aprobãrile necesare ºi, în caz afirmativ, care este suma maximã de bani care îi rãmâne în buzunar la
ieºirea din clãdire.
Date de intrare
Fiºierul de intrare taxe.in conþine pe prima linie numerele S ºi n, despãrþite printr-un spaþiu, iar pe urmãtoarele
n linii câte n numere separate prin spaþii care reprezintã taxele cerute de funcþionarii din fiecare birou.
Date de ieºire
Fiºierul de ieºire taxe.out conþine o singurã linie pe care se aflã numãrul maxim de euro care îi rãmân în buzunar
sau valoarea -1 dacã investitorului nu-i ajung banii pentru a obþine aprobarea.

EX:
10 3

1 2 5
1 3 1
0 8 1
solutia se obtine trecand prin casutele(1,1),(2,1),(2,2),(2,3),(3,3)

Problema se gaseste in gazeta informatica nr 15/2(nu am inteles rezolvarea lor, iar algoritmul lui lee nu vad cum l-as folosi aici, acesta practic numara, numarul de casute, de la o casuta de start la oricare casuta din matrice(cam asta am inteles eu), nu prea stiu cum ajuta in cazul de fata).
Cei care aveti idei in solutionarea problemei v-as fi foarte recunoscator daca ati impartasi-o cu mine.
Aici aveti si linkul catre site-ul gazetei: http://www.ginfo.ro/revista/15_2/focus1.pdf

Va multumesc!

[•gabitzish1]

Mai pune'te cu burta pe algoritmul Lee pana'l intelegi, si o sa stii sa'l aplici si aici.
La lee'ul pe care l'ai inteles tu, bagi in coada "casutele" nevizitate sau cele vizitate dar la care poti ajunge cu un numar mai mic de pasi.
Aici trebuie sa bagi in coada "camerele" nevizitate sau cele vizitate dar in care poti ajunge platind o taxa mai mica. Adica, nu te intrebi daca m[xNou][yNou] > m[xVechi][yVechi] + 1 ci daca m[xNou][yNou] > m[xVechi][yVechi] + taxa[xNou][yNou]. Sper ca ai priceput ceva, ca nu'i greu

[•Mishu91]

Aici nu trebuie să folosești algoritmul lui Lee propriu-zis, ci trebuie să vezi cum îl adaptezi. Așadar, trebuie să faci ceva asemănător algoritmului Bellman - Ford. Din fiecare căsuță a matricii mergi în căsuțele vecine (le bagi în coadă) doar dacă soluția se îmbunătățește. Mai pe scurt, să zicem că ai ești în căsuța (i, j), cu costul c. Merg în căsuța (i+1, j) doar dacă c+A[ i ][ j ] < Sol [ i ][ j ] iar în acest caz Sol[ i ][ j ] ia valoarea c + A[ i ][ j ], unde A[ i ][ j ] este matricea dată, iar Sol[ i ][ j ] reprezintă costul maxim să ajungi din (1, 1) în (i, j).

[•niovan]

Merci mult baieti pt ajutor . Daca stiti cumva vreun link care sa ma ajute(peste tot se abordeaza acceasi problema-determinarea minimului de muchii de la un nod la celelalte, altceva nu prea am gasit) be free to post it here .

[•mathboy]

Uite aici : http://infoarena.ro/problema/bfs