W Podskokach Do Celu

Zadanie

Dana jest plansza szachowa o pewnym rozmiarze n oraz pole początkowe skoczka oraz docelowe. Ile ruchów musi wykonać skoczek, aby znaleźć się w punkcie docelowym, o ile może tam dotrzeć? Napisz program, który pozwoli to sprawdzić.

Przykładowo dana jest plansza o rozmiarze n = 5. Skoczek znajduje się pośrodku planszy i ma przejść dwa pola niżej do krawędzi. Oto przykładowa ilustracja rozwiązania:

Na planszy zostały zaznaczone na czerwonawo wszystkie ruchy, które skoczek może wykonać w pierwszym ruchu. Strzałka prowadząca od skoczka wskazuje obrany pierwszy skok, a kolejna prowadzi do punktu docelowego zaznaczonego kolorem zielonym. Oczywiście istnieje również drugie rozwiązanie lustrzane. Obydwa wymagają wykonania dwóch ruchów i jest to minimalna ich ilość.

Analiza Zadania

Algorytm można oprzeć o algorytm BFS używany podczas przeglądania grafów. Możliwe przejścia są to możliwe skoki wykonywane przez skoczka z danego miejsca. Warunkiem kończącym kolejne przejścia jest natrafienie na niepoprawne pole, albo na pole już wcześniej odwiedzone.

Implementacja

Część prywatna

Poniższa funkcja ileRuchow() przyjmuje cztery argumenty: pozycję startową skoczka xs, ys, punkt docelowy xc, yc oraz rozmiar planszy n. Jako wynik funkcja zwraca ilość ruchów potrzebnych do osiagnięcia pola docelowego. W przypadku, gdy pole jest nie do osiągnięcia to zwracana jest wartość -1.

1. int ileRuchow(int xs, int ys, int xc, int yc, int n) {
2.   int przejscia[] = { 1, 2, 1, -2, -1, 2, -1, -2,
3.             2, 1, 2, -1, -2, 1, -2, -1 };
4.   bool** plansza = new bool *[n];
5.   for (int x = 0; x < n; x++) {
6.     plansza[x] = new bool[n];
7.     for (int y = 0; y < n; y++) {
8.       plansza[x][y] = false;
9.     }
10.   }
11.   plansza[xs][ys] = true;
12.   queue< pozycja > kolejka;
13.   kolejka.push(utworzPozycje(xs, ys, 0));
14.   while (!kolejka.empty()) {
15.     pozycja teraz = kolejka.front();
16.     kolejka.pop();
17.     if (teraz.x == xc && teraz.y == yc) {
18.       return teraz.ruch;
19.     }
20.     for (int i = 0; i < 16; i += 2) {
21.       int x = teraz.x + przejscia[i];
22.       int y = teraz.y + przejscia[i + 1];
23.       if (sprawdzPole(x, y, n) && !plansza[x][y]) {
24.         plansza[x][y] = true;
25.         kolejka.push(
26.           utworzPozycje(x, y, teraz.ruch + 1)
27.           );
28.       }
29.     }
30.   }
31.   return -1;
32. }

Na początku deklarowane są możliwe przejścia oraz tablica wartości logicznych, gdzie będzie zapisywane czy dane pole zostało już odwiedzone. Nastepnie oznaczane jest jako odwiedzone pole startowe skoczka i zostaje ono dodane do kolejki. Następnie dopóki kolejka nie jest pusta to pobierana jest pierwsza pozycja w kolejce i jeśli aktualne pole to pole docelowe to zwracana jest liczba ruchów ile potrzeował skoczek by dotrzeć na to pole. Jednak jeśli pole nie zostało osiagnięte to do kolejki dodawane są wszystkie osiągalne pola z danej pozycji zgodnie z ruchami skoczka.

Dodatkowo w algorytmie została wykorzystana dodatkowa funkcja, która sprawdza czy dane pole znajduje się na planszy.

1. bool sprawdzPole(int x, int y, int n) {
2.   return (x >= 0 && y >= 0 && x < n && y < n);
3. }

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z poniższego fragmentu kodu. Wczytuje on od użytkownika dane, a następnie wypisuje komunikat na podstawie wyniku.

1. int main() {
2.   int n, xs, ys, xc, yc;
3.   cout << "Podaj rozmiar planszy:\n n = ";
4.   cin >> n;
5.   cout << "Podaj pozycje skoczka (x, y)\n s = ";
6.   cin >> xs >> ys;
7.   cout << "Podaj pozycje celu (x, y)\n c = ";
8.   cin >> xc >> yc;
9.   int wynik = ileRuchow(xs, ys, xc, yc, n);
10.   if (wynik == -1) {
11.     cout << "Nie mozna osiagnac celu";
12.   } else {
13.     cout << "Potrzebnych ruchow: " << wynik;
14.   }
15.   system("pause");
16.   return 0;
17. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który do wyznaczenia kolejnych przejść skoczka nie będzie wykorzystywać tablicy, a wyliczy je np. na podstawie, który skok skoczek chce wykonać (np. skok 0 to skok [2, 1]).

• Kod źródłowy Zadanie 1