Strona główna » Algorytmy » Artykuły » Najszybciej do Rogu!
 

Najszybciej do Rogu!

https://mattomatti.com/a0234

Zadanie

Dana jest mapa labiryntu opisana zerami (wolne pole) i jedynkami (zajęte pole). Napisz program, który znajdzie najkrótszą drogę do dowolnego rogu mapy. Można się poruszać tylko lewo, prawo, góra i dół. Jako dane na wejściu otrzyma rozmiar planszy (w, h), zapis labiryntu w postaci macierzy zer i jedynek o podanym wcześniej rozmiarze oraz punkt startowy. Wiersze i kolumny indeksujemy od 0.

Przykład

Przypuśćmy, że dana jest następująca mapa labiryntu o wymiarach 8x6.

01110000
01110110
00000011
11101001
1110S101
11111100

Pole z wartością S wskazuje na punkt początkowy (4, 4). Można z niego osiągnąć trzy rogi z czterech w następującej ilości kroków: lewy, górny w 8 krokach, prawy, górny w 9, a ostatni prawy, dolny w 10. Ostateczna odpowiedź to oczywiście 8.

Analiza Zadania

W celu rozwiązania tego zadania można skorzystać z schematu przeszukiwania wszerz BFS. Mianowicie na początku na kolejkę pól wrzucane jest pole startowe. Następnie dla każdego punktu w kolejce sprawdzamy sąsiednie pola (na górze, na dole, po prawej i po lewej). Przy każdym przejściu zwiększamy aktualną odległość o 1. Jeśli zostanie napotkany róg planszy to aktualizujemy minimalną odległość do rogu o ile aktualna odległość jest mniejsza niż zapisana.

Taki algorytm będzie przeglądać wszystkie możliwe pola, ale proces ten można ograniczyć poprzez sprawdzenie czy dodawane pole do kolejki ma odległość mniejszą niż aktualne minimum. Dzięki temu nie będą sprawdzane pola, które i tak nie ma ją szans wskazać najkrótszej ścieżki. Dodatkowo należy pamiętać, że na samym początku trzeba sprawdzić czy punkt startowy nie jest w rogu. Wtedy wynikiem jest wartość 0.

Implementacja

Dane

Podczas przeglądania mapy będzie potrzebne zapisanie aktualnie przeglądanych pól oraz ich aktualnej odległości. Ułatwi to struktura Dane.

C++C#
Python
  1. class Dane:
  2. def __init__(odleglosc, punkt):
  3. self.odleglosc = odleglosc
  4. self.punkt = punkt

Typ pola

W tym zadaniu ważne jest, aby móc sprawdzić czy dane pole nie jest rogiem planszy. Funkcja CzyRog() odpowiada na to pytanie. Wystarczy podać rozmiar planszy oraz aktualnie przeglądaną pozycję.

C++C#
Python
  1. def CzyRog(rozmiar, poz):
  2. return (poz.X % (rozmiar.X - 1) == 0
  3. and poz.Y % (rozmiar.Y - 1) == 0)

W przedstawionym w dalszej częściu algorytmu program na ślepo wyznacza kolejne pola, dlatego należy sprawdzić funkcją CzyOk() czy dane pole istnieje.

C++C#
Python
  1. def CzyOk(rozmiar, poz):
  2. return (poz.X >= 0 and poz.Y >= 0
  3. and poz.X < rozmiar.X and poz.Y < rozmiar.Y)

Funkcja główna

Oto kod głównej funkcji SzukajDrogi(), która dla danej macierzy o rozmiarze rozmiar i danym punkcie startowym punktStart zwróci najkrótszą odległość do dowolnego rogu planszy.

C++C#
Python
  1. def SzukajDrogi(macierz, rozmiar, punktStart):
  2. if (CzyRog(rozmiar, punktStart)):
  3. return 0
  4. q = []
  5. min = sys.maxsize
  6. start = Dane(0, punktStart)
  7. macierz[start.punkt.Y][start.punkt.X] = 1
  8. q.append(start)
  9. przes = [
  10. Point(0, 1), Point(0, -1),
  11. Point(1, 0), Point(-1, 0)
  12. ]
  13. while (q.Count != 0):
  14. aktualny = q.pop()
  15. if (CzyRog(rozmiar, aktualny.punkt)
  16. and aktualny.odleglosc < min):
  17. min = aktualny.odleglosc
  18. continue
  19. for k in range(4):
  20. nastepny = Point(
  21. aktualny.punkt.X + przes[k].X,
  22. aktualny.punkt.Y + przes[k].Y
  23. )
  24. nowy = Dane(aktualny.odleglosc + 1, nastepny)
  25. if (CzyOk(rozmiar, nowy.punkt)
  26. and macierz[nowy.punkt.Y][nowy.punkt.X] == 0
  27. and nowy.odleglosc < min):
  28. q.append(nowy)
  29. macierz[nowy.punkt.Y][nowy.punkt.X] = 1
  30. return min

Na początku algorytm sprawdza czy start nie znajduje się w rogu. W przeciwnym razie przechodzimy do inicjalizacji kolejki i umieszczamy na niej punky startowy. Deklarowane są również możliwe przesunięcia względem aktualnie wybranego punktu. Następnie dopóki kolejka nie jest pusta pobieramy pierwszy element i jeśli jest narożnikiem to aktualizujemy aktualne minimum. Potem wyliczamy sąsiednie pola i dodajemy do kolejki tylko te, które spełniają warunek.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu:

C++C#
Python
  1. data = input("Podaj rozmiary labiryntu\n w, h = ").split()
  2. rozmiar = Point(int(data[0]), int(data[1]))
  3. print("Podaj elementy macierzy:")
  4. macierz = []
  5. for i in range(0, n):
  6. tab = [int(x) for x in input().split()]
  7. macierz.append(tab)
  8. data = input("Podaj punkt początkowy\n x, y = ").split()
  9. start = Point(int(data[0]), int(data[1]))
  10. wynik = SzukajDrogi(macierz, rozmiar, start)
  11. if (wynik == sys.maxsize):
  12. print("Nie istnieje trasa do rogu!")
  13. else:
  14. print("Najbliższy róg jest w odległości", wynik)

Jako dane testowe można podać następujące dane:

  1. 8 6
  2. 0 1 1 1 0 0 0 0
  3. 0 1 1 1 0 1 1 0
  4. 0 0 0 0 0 0 1 1
  5. 1 1 1 0 1 0 0 1
  6. 1 1 1 0 0 1 0 1
  7. 1 1 1 1 1 1 0 0
  8. 4 4