Najszybciej do Rogu!

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.

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.

1. struct Dane {
2.   int odleglosc;
3.   Point punkt;
4. };

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ę.

1. bool CzyRog(Point rozmiar, Point poz) {
2.   return (poz.X % (rozmiar.X - 1) == 0
3.     && poz.Y % (rozmiar.Y - 1) == 0);
4. }

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

1. bool CzyOk(Point rozmiar, Point poz) {
2.   return poz.X >= 0 && poz.Y >= 0
3.     && poz.X < rozmiar.X && poz.Y < rozmiar.Y;
4. }

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.

1. int SzukajDrogi(int** macierz, Point rozmiar, Point punktStart) {
2.   if (CzyRog(rozmiar, punktStart)) {
3.     return 0;
4.   }
5.   queue<Dane> q;
6.   int min = INT_MAX;
7.   Dane start;
8.   start.odleglosc = 0;
9.   start.punkt = punktStart;
10.   macierz[start.punkt.Y][start.punkt.X] = 1;
11.   q.push(start);
12.   Point przes[] = {
13.     Point(0, 1), Point(0, -1),
14.     Point(1, 0), Point(-1, 0)
15.   };
16.   while (q.size() != 0) {
17.     Dane aktualny = q.front();
18.     q.pop();
19.     if (CzyRog(rozmiar, aktualny.punkt)
20.       && aktualny.odleglosc < min) {
21.       min = aktualny.odleglosc;
22.       continue;
23.     }
24.     for (int k = 0; k < 4; k++) {
25.       Dane nowy;
26.       nowy.odleglosc = aktualny.odleglosc + 1;
27.       nowy.punkt = Point(
28.         aktualny.punkt.X + przes[k].X,
29.         aktualny.punkt.Y + przes[k].Y
30.       );
31.       if (CzyOk(rozmiar, nowy.punkt)
32.         && macierz[nowy.punkt.Y][nowy.punkt.X] == 0
33.         && nowy.odleglosc < min) {
34.         q.push(nowy);
35.         macierz[nowy.punkt.Y][nowy.punkt.X] = 1;
36.       }
37.     }
38.   }
39.   return min;
40. }

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:

1. int main() {
2.   int w, h, X, Y;
3.   cout << "Podaj rozmiary labiryntu\n w, h = ";
4.   cin >> w >> h;
5.   cout << "Podaj mape:" << endl;
6.   int** macierz = new int*[h];
7.   for (int i = 0; i < h; i++) {
8.     macierz[i] = new int[w];
9.     for (int j = 0; j < w; j++) {
10.       cin >> macierz[i][j];
11.     }
12.   }
13.   cout << "Podaj pozycje poczatkowa\n x, y = ";
14.   cin >> X >> Y;
15.   int wynik = SzukajDrogi(macierz, Point(w, h), Point(X, Y));
16.   if (wynik == INT_MAX) {
17.     cout << "Nie istnieje trasa do rogu!";
18.   }
19.   else {
20.     cout << "Najblizszy rog jest w odleglosci " << wynik;
21.   }
22.   system("pause");
23.   return 0;
24. }

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

• Kod źródłowy Implementacja