Budżet: 1000 UAH Termin: 1 dzień
Witam.
Już zrealizowałem rozwiązanie dla tego zadania.
Program napisany jest w ANSI C / C89 bez użycia C++ i zewnętrznych bibliotek. Implementacja odpowiada formatowi z PDF: odczytuje plik wejściowy z argumentu wiersza poleceń, przetwarza komendy L do dodawania poziomych lub pionowych ścieżek oraz komendy Q do sprawdzania spójności dwóch punktów.
Do zadania wykorzystano Union-Find / DSU, ponieważ trzeba nie szukać trasy, a określić, czy dwa punkty należą do jednej komponenty spójności. Zrobiłem również zoptymalizowaną wersję: użyto iteracyjnego find dla DSU oraz dodatkowych tablic skip, aby nie przechodzić ponownie przez już przetworzone części poziomych i pionowych ścieżek. To zmniejsza liczbę zbędnych operacji na nakładających się lub długich odcinkach.
Kod kompiluje się przez GCC poleceniem:
gcc -ansi -Wall -Wextra -pedantic main.c mfset.c -o pcb.exe
Po kompilacji uzyskano kod wyjścia 0. W teście program poprawnie wyświetla wyniki w formacie C / NC bez zbędnego tekstu.
Na wyjściu przekażę:
- main.c;
- mfset.c;
- mfset.h;
- testowy input.txt;
- polecenie do kompilacji i uruchomienia;
- w razie potrzeby zbudowany pcb.exe.
