Zadanie skoczek[B] Potyczki Algorytmiczne 2009

Question

Nie potrafię wymyślić algorytmu do zadania skoczek[B] Potyczki Algorytmiczne 2009. Jeśli miałby ktoś jakiś pomysł jak to rozwiązać to proszę o podpowiedź.

 

Z góry dziękuje.

Link do zadania: http://main.edu.pl/pl/archive/pa/2009/kns

Answer 1

Musisz sprawdzić wszystkie możliwe ruchy. Poszukaj sobie w google o sposobach przeszukiwania grafu, zobacz jak wygląda DFS i BFS. Przykładowo dajesz na stos wszystkie możliwe ruchy w danej pozycji po czym, w dwuwymiarowej tablicy typu bool ustawiasz obecną pozycję na true czyli już sprawdzoną aby drugi raz w nią nie wlazło. Myślę że sobie poradzisz.

Comments

w zadaniu jest mowa o nieskończonej szachownicy, więc nie da się sprawdzić wszystkich możliwych ruchów.