![](/static/branding/mistrzostwa/map_logo.jpg)
![](/static/branding/mistrzostwa/nask_logo.png)
![](/static/branding/mistrzostwa/cp_logo.png)
![](/static/branding/mistrzostwa/uwr_logo.png)
![](/static/branding/mistrzostwa/fri_logo.png)
![](/static/branding/mistrzostwa/insert_logo.png)
Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023
Problem description
Wiktor walczy z zadaniem Zamek z XXIV Olimpiady Informatycznej. Zadanie ma już prawie rozwiązane, ale niestety, nie działa na niektórych przygotowanych przez niego testach. Wiktor mógłby łatwiej zdebugować program, gdyby przygotowane przez niego testy mógł wyświetlić w terminalu.
Mapa zamku naniesiona jest na układ współrzędnych i mieści się w całości w prostokącie, którego lewy dolny róg znajduje się w punkcie (0,0), a prawy górny róg w (w,h). Zamek dzieli się na komnaty, które w całości wypełniają zamek. Jedna z komnat jest komnatą początkową, a jedna końcową. Niektóre z komnat mogą być zablokowane. Napisz kod, który wczyta opis zamku i narysuje go jako ASCII-art na ekranie!
Wejście
W pierwszym wierszu standardowego wejścia znajdują się cztery liczby naturalne w, h, N i M, oznaczające odpowiednio wymiar mapy, liczbę komnat zamku oraz liczbę blokad. W drugim wierszu znajduje się para liczb xp, yp oznaczające współrzędne punktu początkowego. W trzecim wierszu znajdują się liczby xs, ys oznaczające współrzędne punktu końcowego. Obie pary współrzędnych znajdują się wewnątrz pewnej komnaty (a nie na brzegu).
W następnych N wierszach znajdują się opisy komnat, i-ty z nich zawiera cztery liczby całkowite x1, y1, x2, y2 oznaczające, że prostokąt odpowiadający i-tej komnacie ma przeciwległe wierzchołki w punktach (x1,y1) oraz (x2,y2).
W następnych M wierszach znajdują się opisy blokad. i-ty z nich składa się z dwóch liczb całkowitych x, y oznaczających, że komnata zawierająca punkt (x,y) jest zablokowana.
Wyjście
Na wyjściu należy narysować ASCII-art odpowiadający mapie zamku. Ze
względu na to, że wszystkie znaki mają tę samą szerokość i wysokość,
należy myśleć, że osie pionowe i poziome układu współrzędnych (tj.
wszystkie proste pionowe i poziomie przechodzące przez
punkty kratowe) mają tę samą szerokość i wysokość, co kwadraty 1 × 1 pomiędzy nimi. Zatem pierwsze pole
pierwszego wiersza wyjścia reprezentuje punkt (0,h), a pole o rogach w (0,h) oraz (1,h−1) reprezentuje drugi znak
drugiego wiersza. Rogi wszystkich komnat powinny zostać oznaczone
znakiem +
. Pionowe ściany komnat powinny zostać narysowane
przy użyciu znaków |
, poziomie przy pomocy -
.
Punkt początkowy powinien zostać oznaczony przy pomocy pojedynczego
znaku P
. Punkt końcowy powinien zostać oznaczony przy
pomocy pojedynczego znaku S
. Zablokowane komnaty powinny
zostać w całości wypełnione znakami X
. W
innym razie powinny być wypełnione znakami spacji. Dla rozjaśnienia
zalecane jest zapoznanie się z testem przykładowym.
Ograniczenia
1 ≤ w, h ≤ 2000, 1 ≤ N, M ≤ 1 000 000, wszystkie współrzędne x, y spełniają nierówności 0 ≤ x ≤ w, 0 ≤ y ≤ h.
W testach wartych 50% punktacji zachodzi dodatkowy warunek M = 0 (tzn. nie występują żadne blokady).
Przykład
Wejście | Wyjście | |
|
|
Wejście | Wyjście | |
|
|