Węże i Drabiny

Zadanie

Jaś zastanawia się w ile ruchów może dojść na metę w grze Węże i Drabiny. Napisz program, który pomoże Jasiowi znaleźć odpowiedź dla dowolnej planszy jaką tylko sobie wymyśli.

O grze

Gra polega na wylosowaniu kostką wartości o ile pól do przodu ma się poruszyć gracz. Wygrywa ten kto jako pierwszy dotrze na ostatnie pole. Na planszy znajdują się drabiny oraz węże, które łączą dwa pola na planszy. W momencie, gdy stanie się na dół drabiny to należy przejść na jej szczyt, a jeśli stanie się na ogon węża to ssssspada się na pole wskazane przez głowę węża.

Przykładowa plansza

Przykładowo na powyższej planszy można przeskoczyć z pola 5 na 8, albo spaść z 6 na 1. Grając kostką do gry K3 (można wylosować tylko 1, 2, 3) to grę można ukończyć w 3 ruchy tj. 1 - 4 - (5 - 8) - 9, ale nie można 1 - 4 - 6 - 9.

Implementacja

Opis

Zadanie można rozwiązać rekurencyjnie. W każdym wywołaniu symulujemy przejście o 1, 2, .., 6 pól do przodu. Algorytm kończy działanie, gdy dotrze na linie mety. Należy jednak pamiętać, aby zapobiec nieskończonej rekurencji, ponieważ każdy wąż (tj. cofnięcie) tworzy nieskończony cykl. Można tego uniknąć poprzez wykrycie, że następne pole jest wcześniej niż aktualne.

Rozpoczęcie poszukiwań

Na podstawie przekazanego rozmiaru planszy n oraz przejść tworzona jest tablica, która na i-tej pozycji ma zapisane faktyczne pole docelowe po przejściu na nie. W przypadku zwykłego pola na i-tej pozycji jest i, ale dla ogona węża czy początku drabiny wartością będzie pole docelowe przejścia. Funkcja zwraca wynik wyszukiwania ruchu.

1. int szukajRuchow(int n, vector< pair<int, int> > przejscia) {
2.   int* tab = new int[n];
3.   for (int i = 0; i < n; i++)
4.     tab[i] = i;
5.   for each(pair<int, int> para in przejscia)
6.     tab[para.first] = para.second;
7.   return szukajRuchow(n, tab, 0, 0);
8. }

Symulacja ruchów

Funkcja szukajRuchow() sprawdza kolejne, możliwe ruchy i jako wynik podaje najmniejszy podwynik z dalszych wywołań. Jako argumenty wymaga podania: n - rozmiar planszy, przejscia - przygotowana tablica przejść, teraz - aktualny numer pola oraz ruchow - ile ruchów do tej pory wykonano.

1. int szukajRuchow(int n, int * przejscia, int teraz, int ruchow) {
2.   if (teraz == n - 1) {
3.     return ruchow;
4.   }
5.   int min = n + 1;
6.   for (int i = 1; i <= 6; i++) {
7.     if (teraz + i >= n)
8.       continue;
9.     int nastepny = przejscia[teraz + i];
10.     if (nastepny < n && nastepny > teraz) {
11.       int wynik = szukajRuchow(n, przejscia, nastepny, ruchow + 1);
12.       if (wynik < min) {
13.         min = wynik;
14.       }
15.     }
16.   }
17.   return min;
18. }

Warunkiem stopu rekurencji jest osiągnięcie pola docelowego. Dla pozostałych pól należy zasymulować ruch o każdą możliwą wartość.

Testowanie funkcji

Do przetestowania napisanego kodu można skorzystać z poniższego fragmentu programu:

1. int main () {
2.   int n, t, a, b;
3.   cout << "Ile gra ma pol?\n n = ";
4.   cin >> n;
5.   cout << "Ile jest przejsc?\n t = ";
6.   cin >> t;
7.   cout << "Podaj pary przejsc (poczatek, koniec)\n";
8.   vector< pair<int, int> > przejscia;
9.   for (int i = 0; i < t; i++) {
10.     cin >> a >> b;
11.     przejscia.push_back(make_pair(a, b));
12.   }
13.   int wynik = szukajRuchow(n, przejscia);
14.   if (wynik == n + 1) {
15.     cout << "Nie mozna ukonczyc planszy";
16.   } else {
17.     cout << "Potrzebnych ruchow: " << wynik;
18.   }
19.   system("pause");
20.   return 0;
21. }

Przykładowo, aby wprowadzić planszę pokazaną na początku artykułu należy wpisać (pola indeksujemy od 0):

1. 9
2. 2
3. 4 7
4. 5 0

• Kod źródłowy Implementacja