Mam tablicę dwuwymiarową n na m. Niektóre komórki są wypełnione liczbami dodatnimi, w pozostałych jest 0.
Chcę znaleźć najbliższą taką komórkę do podanej (x, y) w której jest jakaś liczba dodatnia. Jest jeszcze dodatkowy warunek: że jeśli w tej samej odległości jest kilka liczb dodatnich, to wybrać z nich najmniejszą.
Nie mogę sobie poradzić żeby znaleźć jakąkolwiek niezerową komórkę.
Tak wygląda fragment tablicy z pokazaną odległością od wybranej komórki:
Komórka w środku, to komórka o współrzędnych x,y.
Krok 0: sprawdzam czy komórka o wsp. x i y jest pusta, jeśli nie to wypisuje jej zawartość i koniec. Jeśli jest pusta to
Krok 1: sprawdzam wszystkie komórki w odległości 1, czyli komórkę u góry, na dole, po lewej i po prawej.
Krok 2: sprawdzam wszystkie komórki w odległości 2 itd.
Pomyślałem o napisaniu funkcji rekurencyjnej. O ile z krokiem nr 0 i 1 nie ma problemu, to problem pojawia się gdy chce znaleźć coś w odległości 2 i dalszych. No właśnie, jak to zrobić? To znaczy jak sprawdzić wszystkie komórki w odległości 2 (patrz obrazek), jeśli coś znajdę to zwrócić wynik, a jeśli nie, to sprawdzam w dalszych odległościach.
Zacząłem pisać funkcję, ale nie do końca wiem co dalej. Wiem że to co jest po else, nie jest już dobre, ale może da się to jakoś uratować i tylko wystarczy coś poprawić? A może są już jakieś gotowe algorytmy na przeszukiwanie tablicy w ten sposób?
int sprawdz_sasiada (int x, int y)
{
int najblizszy=infinity;
if (tablica[x-1][y]!=0)
if (tablica[x-1][y]<najblizszy) najblizszy=tablica[x-1][y];
if (tablica[x][y-1]!=0)
if (tablica[x][y-1]<najblizszy) najblizszy=tablica[x][y-1];
if (tablica[x][y+1]!=0)
if (tablica[x][y+1]<najblizszy) najblizszy=tablica[x][y+1];
if (tablica[x+1][y]!=0)
if (tablica[x+1][y]<najblizszy) najblizszy=tablica[x+1][y];
if (najblizszy<infinity) // jesli cos znalazl
return najblizszy;
else // jesli nie, to szukaj glebiej
{
sprawdz_sasiada(x-1, y, k, w);
sprawdz_sasiada(x, y-1, k, w);
sprawdz_sasiada(x, y+1, k, w);
sprawdz_sasiada(x+1, y, k, w);
}
}