Napisać kod w języku C dla zadania
169 PLN
Zadanie konkursowego zadania polega na opracowaniu efektywnego programu, który będzie w stanie rozwiązać łamigłówkę „prostokąty”.
Łamigłówka wprowadzana jest do prostokątnego pola. W polu wprowadzane są puste pola oraz pola z informacjami cyfrowymi. Zadanie polega na tym, aby cała powierzchnia wprowadzonej łamigłówki została podzielona na prostokąty w taki sposób, aby:
- prostokąty pokrywały całą wskazaną powierzchnię,
- prostokąty nie nakładały się na siebie,
- każde wypełnione pole znajdowało się w innym prostokącie,
- rozmiar prostokąta (powierzchni) odpowiadał numerowi wypełnionego kwadratu.
Rozwiązując, wiesz, że obszar gry ma rozmiar nie większy niż 32x32 kwadraty, całkowita liczba wypełnionych kwadratów wynosi nie więcej niż 200, a wypełnione liczby mieszczą się w zakresie od 1 do 99.
Na standardowym wejściu program otrzymuje wejście łamigłówki, wprowadzenie kończy się zakończeniem std. wejścia (EOF aktywne). Dokładny format wejścia można zobaczyć w przykładzie poniżej.
Program analizuje wprowadzone łamigłówki i ustala, który z wariantów wyszedł:
- zapis nieprawidłowy
- wejściem była łamigłówka, która ma tylko jedno prawidłowe rozwiązanie. W takim przypadku program wyświetli to rozwiązanie.
- Wejściem była łamigłówka, której nie udało się złożyć (0 rozwiązań). Program wyświetla informacje o nieudanej próbie.
- Wskazana łamigłówka ma wiele rozwiązań (więcej niż jedno), w takim przypadku program oblicza, na ile sposobów można podzielić powierzchnię. Pod różnymi sposobami podziału rozumie się, że rozkład prostokątów różni się położeniem przynajmniej jednej linii granicznej.
Program musi sprawdzić poprawność wprowadzonych danych. Jeśli w danych wejściowych wprowadzono nieprawidłowe, bezsensowne lub sprzeczne wartości, program to wykrywa, wyświetla komunikat o błędzie i kończy działanie. Format komunikatu o błędzie pokazany jest w przykładzie wykonania poniżej. Błędem jest:
- brak, nieprawidłowa lub niepełna ramka pola,
- zawartość pola różni się od spacji i cyfr 1-99,
- brak oznaczenia kątów pudełka,
- tablica większa niż 32 x 32,
- liczba wypełnionych pól większa niż 200.
Program testowany jest w ograniczonym środowisku. Jest ograniczony objętością dostępnej pamięci oraz czasem wykonania. Oba ograniczenia można zobaczyć w dzienniku testowania rozwiązania z przykładu. Ogólnie rzecz biorąc, zadanie nie wymaga pamięci. Jednak jest bardzo wymagające pod względem czasu procesora. Jeśli łamigłówka ma kilka rozwiązań, zbadanie wszystkich wariantów może zająć bardzo dużo czasu. Należy opracować efektywny algorytm, który pozwoli nie tracić czasu na próby, które nie prowadzą do celu.
Praca oceniana jest w trybie konkursowym. Oznacza to, że jest trudniejsza niż standardowe prace. Wymaga połączenia umiejętności programowania i algorytmizacji. Zakłada się, że zadania będą rozwiązywać studenci, którzy mają pewną wiedzę z programowania, czyli studenci, dla których standardowe zadania są nudne. Ocena składa się z gwarantowanego zestawu punktów (sukces w testach pozakonkursowych) oraz zestawu punktów uzyskanych za miejsce w konkursie z innymi uczniami (te punkty są zaliczane po zakończeniu konkursu).
Przykład pracy programowej:
Wprowadź łamigłówkę:
+--+--+--+--+--+
| 2 3 2|
+ + + + + +
| 2 3 |
+ + + + + +
| 3 |
+ + + + + +
| 2 |
+ + + + + +
| 2 3 3|
+--+--+--+--+--+
Jedno rozwiązanie:
+--+--+--+--+--+
| 2| 3 | 2|
+ +--+--+--+ +
| | 2| 3| |
+--+--+--+ +--+
| 3 | | |
+--+--+--+ + +
| | 2| | |
+ +--+--+--+ +
| 2| 3| 3|
+--+--+--+--+--+
Wprowadź łamigłówkę:
+--+--+--+--+--+--+--+--+--+--+
| 4 2 |
+ + + + + + + + + + +
| 3 |
+ + + + + + + + + + +
| 2 3 8 |
+ + + + + + + + + + +
| 4 2 10 |
+ + + + + + + + + + +
| 2 2 3 |
+ + + + + + + + + + +
| 2 6|
+ + + + + + + + + + +
| 12 6 |
+ + + + + + + + + + +
| 2 4 4|
+ + + + + + + + + + +
| 10 3 |
+ + + + + + + + + + +
| 2 2 2 |
+--+--+--+--+--+--+--+--+--+--+
Jedno rozwiązanie:
+--+--+--+--+--+--+--+--+--+--+
| 4| 2| | | | | | |
+ + + + + + + + + + +
| | | | 3| | | | |
+ +--+ + + + + + + + +
| | 2| | | 3| 8| | |
+ + + +--+--+ + + + + +
| | | 4| 2 | | 10| |
+--+--+--+--+--+--+--+ + + +
| 2| 2| 3 | | |
+--+--+--+--+--+--+--+--+--+ +
| | | 2| 6|
+ + + + + + + + + +--+
| 12| 6 | | |
+--+--+--+--+--+--+ + +--+ +
| 2 | 4 | | | 4|
+--+--+--+--+--+--+--+--+ + +
| | | | 10 | 3| |
+ + + + + + + + + + +
| 2| 2| 2| | | |
+--+--+--+--+--+--+--+--+--+--+
Wprowadź łamigłówkę:
+--+--+--+--+--+--+--+--+--+
| 2 3 2 |
+ + + + + + + + + +
| 3 2 2 1 |
+ + + + + + + + + +
| 7 |
+ + + + + + + + + +
| 7 3 |
+ + + + + + + + + +
| 4 4 3 3 7|
+ + + + + + + + + +
| 3 |
+ + + + + + + + + +
| 4 3 |
+--+--+--+--+--+--+--+--+--+
Jedno rozwiązanie:
+--+--+--+--+--+--+--+--+--+
| 2| 3| | | 2 | |
+ +--+--+--+ + +--+--+ +
| | 3| 2| 2| 1| | |
+--+--+--+--+--+--+--+ + +
| 7 | | |
+--+--+--+--+--+--+--+ + +
| 7 | 3| |
+--+--+--+--+--+--+--+--+ +
| 4| 4| 3| 3 | 7|
+ + + + + +--+--+--+ +
| | | | 3 | |
+--+--+--+--+ +--+--+--+ +
| 4 | | 3 | |
+--+--+--+--+--+--+--+--+--+
Wprowadź łamigłówkę:
+--+--+--+--+
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4|
+--+--+--+--+
Łącznie rozwiązań: 9
Wprowadź łamigłówkę:
+--+--+--+--+--+--+--+--+--+
| 3 3 |
+ + + + + + + + + +
| 4 4 3 2 2 3 |
+ + + + + + + + + +
| 2 |
+ + + + + + + + + +
| 4 2 3 |
+ + + + + + + + + +
| 3 6 |
+ + + + + + + + + +
| 2 2 2 |
+ + + + + + + + + +
| 2 2 2 8|
+ + + + + + + + + +
| 8 |
+--+--+--+--+--+--+--+--+--+
Łącznie rozwiązań: 39
Wprowadź łamigłówkę:
+--+--+--+--+--+--+
| |
+ + + + + + +
| 12 |
+ + + + + + +
| 2 4 |
+ + + + + + +
| 4 |
+ + + + + + +
| 2 |
+ + + + + + +
| |
+ + + + + + +
| 2 8 |
+ + + + + + +
| 3 5 6|
+--+--+--+--+--+--+
Brak rozwiązania.
Wprowadź łamigłówkę:
+--+--+--+--+--+
| 2 |
+ + + + + +
| 3 2 |
+ + + + + +
| 3 |
+ + + + + +
| |
+ + + + + +
| 2 2 7|
+ + + + + +
| 3 |
+ + + + + +
| 2 7 2 |
+--+--+--+--+--+
Zły wpis.
-
Добрий день. А приклад виконавчої роботи правильно вставився, враховуючи усі відступи? А то не зовсім розумію... Може ви можете прислати безпосередньо файл із завданням?
-
Ukraina