przeszukiwanie dwuwymiarowej tablicy

0

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:
user image

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);
    }
}
0

Użyj algorytm Dijkstry (koszt przejścia zawsze 1).

0

Ale jak skoro tutaj nie mam grafu?

1

Masz graf, każda kratka ma maksimum czterech sąsiadów (góra,dół,lewo,prawo) minimum dwóch dla kratek w rogu.
Ale owszem nie musisz tego implementować w postaci grafu.

0

A jak wczytać ten graf? Podaję tylko rozmiar tabeli i kilka współrzędnych punktów w których są liczby. Jak to przerobić na graf?

0

Nie trzeba tego fizycznie przerabiać na graf, jedynie w wyobraźni.

1 użytkowników online, w tym zalogowanych: 0, gości: 1