pomoc w zrozumieniu programu

Question

cześć potrzebuje pomocy w zrozumieniu tej części programu dotyczącego labiryntu, pan na lekcji dość słabo to wytłumaczył :((( 

 

z góry dzięki za pomoc, 

andrzej

bool Droga(int Lab[][N], int w, int k)
{
    Lab[w][k] = 1;

    if(w == 0 || w == N-1 || k == 0 || k == N-1)
        return true;

    if(Lab[w-1][k] == 0 && Droga(Lab, w-1, k))
        return true;

    if(Lab[w+1][k] == 0 && Droga(Lab, w+1, k))
        return true;

    if(Lab[w][k-1] == 0 && Droga(Lab, w, k-1))
        return true;

    if(Lab[w][k+1] == 0 && Droga(Lab, w, k+1))
        return true;

    return false;
}

 

Answer 1

Wydaje mi się, że to jest funkcja sprawdzająca, czy jest wyjście z labiryntu.

W pierwszej linii zaznacza, że tędy przeszła, a w następnych po kolei próbuje szukać, czy da się pójść w danym kierunku. Zmienne w i k odpowiadają za pozycję w labiryncie. Jeżeli znajdzie drogę, to zwraca true, jeśli nie znajdzie to zwraca false.

bool Droga(int Lab[][N], int w, int k) /*
        Lab - labirynt,
        w - pozycja w jednej osi,
        k - pozycja w drugiej osi,
        zwracana wartość - czy da się wyjść z labiryntu zaczynając od danej pozycji
*/ {
    Lab[w][k] = 1; // zaznaczamy, że tędy już przeszliśmy
 
    if(w == 0 || w == N-1 || k == 0 || k == N-1)
        // jeśli wyszliśmy, czyli jesteśmy na którymś brzegu
        return true; // zwracamy true i kończymy
 
    if(Lab[w-1][k] == 0 && Droga(Lab, w-1, k))
        // w przeciwnym wypadku sprawdzamy czy możemy pójść w lewo o jedno pole
        //i czy potem da się pójść dalej (po to wywołuje się Droga() na następnym polu)
        return true; // jeśli uda się przejść zwracamy true i kończymy
 
    if(Lab[w+1][k] == 0 && Droga(Lab, w+1, k))
        // w przeciwnym wypadku sprawdzamy, czy możemy pójść w prawo o jedno pole
        //i czy potem da się pójść dalej
        return true; // jeśli uda się przejść zwracamy true i kończymy
 
    if(Lab[w][k-1] == 0 && Droga(Lab, w, k-1))
        // w przeciwnym wypadku sprawdzamy, czy możemy pójśc w dół o jedno pole
        //i czy potem da się pójść dalej
        return true; // jeśli uda się przejść zwracamy true i kończymy
 
    if(Lab[w][k+1] == 0 && Droga(Lab, w, k+1))
        // w przeciwnym wypadku sprawdzamy, czy możemy pójść w górę o jedno pole
        //i czy potem da się pójśc dalej
        return true; // jeśli uda się przejść zwracamy true i kończymy
 
    return false; // w przeciwnym wypadku oznacza to, że nie da się wyjść z labiryntu 
                  //idąc w jakąkolwiek stronę, więc zwracamy false i kończymy
}

 

Comments

 if(Lab[w-1][k] == 0 && Droga(Lab, w-1, k))
        // w przeciwnym wypadku sprawdzamy czy możemy pójść w lewo o jedno pole
        //i czy potem da się pójść dalej (po to wywołuje się Droga() na następnym polu)
        return true; // jeśli uda się przejść zwracamy true i kończymy

nie ma tu przeciwnego przypadku ... bo rekurencyjnie wykonujemy funkcje zanim warunek "jest prawdziwy" :) ... więc jeśli to nie zwróci wartości tu nie ma alternatywy 

Droga(Lab, w-1, k) wykonuje się jeśli poprzednik koniunkcji czyli Lab[w-1][k] ==0 jest prawdziwe, to i tak rekurencja już wystartuje.