Kurs "Main" - Zadanie "Krokodyle"

Witam :)

Przerabiam zadania z tego kursu i mam problem z zadaniem o Krokodylach (link).

Rozwiązałem to zadanie przez rekurencję (musiałem rozważyć 7 przypadków w zależności od położenia aktualnego i poprzedniego na przeszkodzie oraz początkowych wartości a oraz b), ale oczywiście dla 3 przypadku przez przeładowanie stosu program się liczy bardzo długo.

Widziałem rozwiązanie z pętlą (link), ale szczerze mówiąc go nie rozumiem.

Czy ktoś mógłbym mi wyjaśnić jak zliczać te drogi przez pętlę? Będę bardzo wdzięczny.

unsigned int noWays(unsigned short int act_width, unsigned int act_height, unsigned short int prev_width, unsigned int prev_height,  unsigned short int a, unsigned int b){
	
	if (act_height == b)
		return 1;
	
	if (prev_height < act_height){
		if (act_width == 0)
			return noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
		else if (act_width == a)
			return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b);
		else
			return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
	} else {
		if (prev_width > act_width){
			if (act_width == 0)
				return noWays(act_width, act_height + 1, act_width, act_height, a, b);
			else
				return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b);
		} else {
			if (act_width == a)
				return noWays(act_width, act_height + 1, act_width, act_height, a, b);
			else
				return noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
		}		
	}	
}

int main(){
	SetConsoleOutputCP(CP_UTF8);
	//	Deklaracja zmiennych
	unsigned short int p, a;
	unsigned int b, w;
	p = giveNumberOfObstacles(1, pow(10, 4));

	for (int i = 0; i < p; ++i){
		a = giveWidth(1, pow(10, 4));
		b = giveHeight(1, pow(10, 9));

		w = noWays(0, 1, 0, 0, a, b);
		cout << "Przeszkodę o wymiarach " << a << "x" << b << " - liczba sposobów na jaką można ją pokonać można pokonać na " << (a + 1) * w << endl;
	}	
}

załóżmy że a to szerokość a b to poziomy.
każdy kolejny poziom możemy przejść na (a+1) sposobów. (Przez to że a to ilość kwadratów, a podróżnik porusza się po krawędziach)
dla:
b=1 mamy (a+1) sposobów
b=2 (a+1)x(a+1) sposobów
b=3 (a+1)x(a+1)x(a+1) sposobów
....

wychodzi nam wzór: wynik = (a+1)^b
Limity czasowe są skonstruowane tak, aby poznać technikę szybkiego potęgowania

@Suchy702: Bardzo dziękuję za dotychczasoww wyjaśnienie.
Rozumiem jak pierwszy poziom przejść na a+1 sposobów, ale dlaczego 2 poziom to (a + 1) × (a +1).
Przecież z niektórych miejsc (krawędzie boczne) można poprowadzić 2 ścieżki, a z innych środkowych 3 ścieżki. Nie rozumiem tego przejścia po prostu :(
W jaki sposób dostajemy to mnożenie, to mnie najbardziej zastanawia?

Bo wchodzisz z (a+1) miejsc zaś wychodzisz z również (a+1) miejsc.

Przyjmijmy dla czytelności, że podróżnik nie idzie po krawędziach, a po kratkach (dlatego zaczynamy od 0):

Nadal nie pasuje, zobacz że dla 1x4 odpowiedź jest 16 zaś wg ciebie (4+1)^1=5. To jakiś chrzan!

Rozwiązanie od Suchy702 jako działający kod (tyle, że przytoczony algorytm szybkiego potęgowania to za mało):
https://godbolt.org/z/d1o3W8n1f

@MarekR22:

Ja mam ostatecznie takie rozwiązanie:
Nie robiłem a % 10000 bo założenia a ma być z przedziału (1, 10000)

unsigned int noWays_fast_power(unsigned short int a, unsigned int b){
	// Złożoność czasowa: O (log_{2}(b))
	if (b == 1)
		return a;
	
	unsigned int w;

	if (b % 2 == 0) {
		w = noWays_fast_power(a, b / 2);
		return w*w % 10000;  // Ponieważ wynik może być duży to zwracamy resztę z dzielenia przez 10000
	} else {
		w = noWays_fast_power(a, b-1);
		return a*w % 10000;  // Ponieważ wynik może być duży to zwracamy resztę z dzielenia przez 10000
	}
	
}
int main(){
	SetConsoleOutputCP(CP_UTF8);
	//	Deklaracja zmiennych
	unsigned short int p, a;
	unsigned int b, w;
	p = giveNumberOfObstacles(1, pow(10, 4));

	for (int i = 0; i < p; ++i){
		a = giveWidth(1, pow(10, 4));
		b = giveHeight(1, pow(10, 9));

		w = noWays_fast_power(a+1, b);
		cout << "Przeszkodę o wymiarach " << a << "x" << b << " - liczba sposobów na jaką można ją pokonać można pokonać na " << w << endl;
	}	
}

Witold Chodor napisał(a):

@MarekR22:

Ja mam ostatecznie takie rozwiązanie:
Nie robiłem a % 10000 bo założenia a ma być z przedziału (1, 10000)

???
W treści jest:

Dla każdej przeszkody oblicz, na ile sposobów Pteppic może ją pokonać. Ponieważ mogą to być duże liczby,
wystarczy że podasz ich resztę z dzielenia przez 10000 (na przykład zamiast 131072 wypisz 1072, a zamiast
10023 – 23).