Implementacja algorytmu Breadth First Search (Chess problem)

Nigdzie nie mogłem znaleźć rozwiązania tego problemu, więc here it goes:

Jesteście Koniem (czyli macie zakres ruchów Skoczka) na szachownicy, zaczynacie na pozycji [0,0] (lewy górny róg) i macie przejść najkrótszą możliwą drogą do prawego dolnego rogu [targetX,targetY], Szachownica ma wymiary od 100 do 1kk, i na wejściu otrzymujecie jagged array w postaci Array[][], a w returnie trzeba zwrócić liczbę kroków które były potrzebne do wykonania. Im algorytm jest wydajniejszy, tym lepiej.

Czy ktoś ma może pomysł jak się za to zabrać? Jedyne implementacje jakie widziałem dotyczyły tablic dwuwymiarowych a nie tablic nieregularnych, ale jeżeli ktoś by coś znalazł to chętnie bym na to rzucił okiem.

Chodzi mi oczywiście o implementacje w C# :)

Czemu w tytule jest Breadth First Search?

lion137 napisał(a):

Czemu w tytule jest Breadth First Search?

W tytule jest Breadth First Search bo po wyszukiwaniu problemu w Google, był on najczęściej wykorzystywany do rozwiązania tego problemu, ale jeżeli jest inaczej, to chętnie to zmienię, po prostu wydawało mi się, że głównym problemem w tym zadaniu jest jego implementacja :)

1. Problem nazywa się Knight's Tour generalnie.
2. Co za różnica dla DFSa jak wygląda graf po którym chodzisz? Przecież to zupełny szczegół. Możesz mieć tablicę i oznaczyć w niej po prostu czy dana krawędź istnieje czy nie, jeśli koniecznie chcesz tablicę.

Ale tu nie ma żadnej filozofii, jest to zwykły BFS.

1. Zdejmujesz pozycję skoczka z kolejki,
2. Wyliczasz 8 nowych pozycji
3. Sprawdzasz które mieszczą się na tej poszarpanej szachownicy
4. Sprawdzasz które jeszcze nie były odwiedzone
5. Dodajesz nowe pozycje na kolejkę
6. powtórz

Można też użyć Dijkstry i innych:
https://stackoverflow.com/questions/2339101/knights-shortest-path-on-chessboard