Jak sprawdzić czy obiekt na tablicy tab[x][y] ma połączenie z tab[0][0]?

Question

Powiedzmy że mamy tablicę intów tab[20][20], i jeżeli tab[x][y] = 0, to jest wolne pole, a jeżeli tab[x][y] = 1, na polu jest droga. Załóżmy też że na tej planszy 20x20 jest jeden obiekt, załóżmy że dom, oraz jakiś dojazd do tej planszy który znajduje się na tab[0][0]. Jak sprawdzić czy tab[x][y] na którym jest dom jest połączony drogą z tab[0][0]? Czytałem trochę o teori grafów ale dalej nie mam pomysłu

*zdjęcie dla ułatwienia (tab[0][0] znajduje się w lewym górnym)*

Answer 1

Fakt, że teoria grafów ma z tym mocny związek, ale niekoniecznie trzeba ją znać. Po prostu jeśli widzisz algorytm do szukania drogi na grafie, wszędzie gdzie widzisz tekst "wierzchołki sąsiadujące z wierzchołkiem X", podmień w głowie na "pola (nie będące ścianami) stykające się z polem X" i wszystko działa tak samo.

Tu jest fajny artykuł z kilkoma różnymi algorytmami o rosnącej złożoności i wydajności, z wytłumaczonym pseudokodem i symulacjami: https://www.redblobgames.com/pathfinding/a-star/introduction.html

(osobę dającą downvote prosiłbym o uzasadnienie)

Answer 2

Teoria grafów: Tablica sąsiadów np, lub macierz sąsiedztwa. Odpowiednie algorytmy ustalające, na podstawie ( powiązanych węzłów grafów za pomocą krawędzi ).

głównie szukaj: macierz sąsiedztwa, tablica sąsiedztwa - tutaj przypadki też z grafami skierowanymi, nieskierowanymi.