Hvala na odgovorima, ja sam malo razmisljao i dosao do sledeceg algoritma:
Dok ne postoji put sastavljen od nula izmadju dve tacke, svaki clan matrice razlicit od nule umanji za 1. Nakon toga jednostavno flood fill-om nadjemo put izmedju dve tacke. dakle pseudo kod ide nekako ovako:
Code:
while (!spojen(A,B))
{
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
if (mat[i][j]!=0)
mat[i][j]--;
}
Gdje funkcija spojen vraca 1 ako postoji put sastavljen od nula izmedju tacke A i B, u suprotnom 0. Nakon ovogo samo opisemo taj put (tu koristimo flood fill algoritam). Nisam jos otkucao kod ali ovo garantovano radi.
Ovo mozemo zamisliti na sledeci nacin:
Ako zamislimo da se iz svakog polja matrice izdize stub visine koja odgovara vrijednosti tog polja i onda takav "model" polako potapamo u vodu, prvi kanal koji se na taj nacin stvori izmedju nase dve tacke predstavlja trazeni put.