Projekt z przedmiotu Teoria Obliczeń i Złożoności Obliczeniowej


Sprawy organizacyjne

Prowadzący przedmiot:

Terminy oddania projektu:

Zaliczenie projektu w terminie późniejszym niż pierwszy skutkuje ocena końcową z przedmiotu nie wyższą niż 3.0.

Do wykonania w ramach projektu:

Języki programowania: Jedyne dwa dopuszczalne języki programowania to C oraz C++.

Współbieżność: Programy nie mogą być wielowątkowe, wieloprocesorowe, itp.

Oceny:

Wymagania na ocenę 3.5

Plansze na oceny 3.5 będą ograniczone do rozmiarów 5x5 (tj., dopuszczalne są, na przykład, plansze o rozmiarach 3x5, 5x5, 5x1, ale---na 3.5---nie będzie plansz o rozmiarach 6x6, 2x6 itp.). Poniżej znajduje się plik z kilkoma przykładowymi planszami podobnymi do tych, które będą wymagane na ocenę 3.5 oraz z programem sedziego (wersja alfa! na razie do uzytku na wlasne ryzyko!).

System arbitrażowy

System arbitrażowy dostępny jest pod następującymi adresami:

Treść zadania

W pewniej bardzo skomplikowanej i niewiarygodnie wręcz tajnej operacji szpiegowskiej bierze udział k agentów. Operacja odbywa się w pewnym mieście X, które zostało przedstawione jako prostokąt zbudowany z x na y kwadratów (y wierszy po x kwadratów) gdzie w środku każdego kwadratu znajduje się skrzyżowanie ulic biegnących w kierunkach północ-południe i wschód-zachód. Naszych k agentów znajduje się na k różnych skrzyżowaniach i ma k różnych skrzyżowań, do których chce się dostać. Aby jednak zminimalizować ryzyko wpadki, każdy agent powinien przejść do swojego docelowego skrzyżowania tak, by na pewno nie spotkać żadnego innego agenta (oczywiście agenc mogą się jedynie poruszać ulicami). Ponieważ nie wiadomo z jakimi prędkościami agenci będą się przemieszczać, ich trasy nie mogą się przecinać w żadnym punkcie.

Zadanie polega na napisaniu programu rozwiązującego problem wyznaczania tras. Program powinien wczytać ze standardowego wejścia opis zadania (rozmiar planszy, ilość agentów oraz pozycje ich obecnych i docelowych skrzyżowań), znaleźć dopuszczalne rozwiązanie i wypisać je na standardowe wyjście.

Opis wejścia i wyjścia

Dane zawsze są w poprawnym formacie i zawsze istnieje przynajmniej jedno poprawne rozwiązanie.

Wejście ma następujący format. W pierwszym wierszu znajdują się dwie liczby, x oraz y, oznaczające rozmiar miasta. Miasto podzielone jest na xy kwadratów (y wierszy po x kwadratów każdy). Można założyć, że:

W drugim wierszu znajduje się pojedyncza liczba k zawierająca ilość agentów w mieście. Mamy:

Następne k wierszy zawiera pozycje agentów i ich docelowych skrzyżowań w następującym formacie: gdzie (xi,yi) to współrzędne skrzyżowania startowego i'go agenta, a (x'i,y'i) to współrzędne jego skrzyżowania docelowego. (Skrzyżowanie w północnozachodnim rogu miasta ma współrzędne (1,1) a to w południowowschodnim (x,y)).

Opis rozwiązania (wyjście) ma następujący format. Pierwszy wiersz zawiera pojedynczą liczbę, s. Kolejne s wierszy jest postaci:

gdzie (xj,yj) oznacza współrzędne skrzyżowania w mieście, a (dxj,dyj) oznacza kierunek, w którym powinien pójść agent, który znajdzie się na tym skrzyżowaniu. Dopuszczalne kierunki to północ, południe, wschód i zachód, opisane jako, odpowiednio, (0,-1), (0,1), (1,0), (-1,0).


Przykładowe wejście i wyjścia

Poniżej znajduje się przykładowe wejście i przykładowe wyjścia.

Wejście:
5 4
2
3 1 5 2
4 1 2 3
Planszę te można graficznie przedstawić jako:


Przykładowe poprawne rozwiązanie:
15
3 1 -1 0
2 1 -1 0
1 1 0 1
1 2 0 1
1 3 0 1
1 4 1 0
2 4 1 0
3 4 1 0
4 4 1 0
5 4 0 -1
5 3 0 -1
4 1 0 1
4 2 0 1
4 3 -1 0
3 3 -1 0
Rozwiązanie można przedstawić graficznie jako:



Przykładowe błędne rozwiązanie (nie wszyscy agenci mają trasę):
11
3 1 -1 0
2 1 -1 0
1 1 0 1
1 2 0 1
1 3 0 1
1 4 1 0
2 4 1 0
3 4 1 0
4 4 1 0
5 4 0 -1
5 3 0 -1
Rozwiązanie można przedstawić graficznie jako:


Przykładowe błędne rozwiązanie (trasy się przecinają):
7
3 1 0 1
3 2 1 0
4 2 1 0
4 1 0 1
4 2 0 1
4 3 -1 0
3 3 -1 0
Rozwiązanie można przedstawić graficznie jako:


Przykładowe błędne rozwiązanie (zmiana pozycji agenta):
4
3 1 0 1
3 2 1 0
4 2 1 0
4 1 1 0
Rozwiązanie można przedstawić graficznie jako:


Kraków, Marzec 2013