Optymalne uzupełnianie tablicy

Question

Cześć! Mam pewien problem i nie wiem, jak go rozwiązać. Jest tu coś na kształt Tetrisa. Mam tablicę dwuwymiarową i w tej tablicy jest tak (na przykład 20 wierszy po 10 kolumn):

................
................
................
##......##..#
#########

Dodatkowo mam sprecyzowane następujące po sobie figury typowo tetrisowe, które mogę obracać i moim zadaniem jest je optymalnie rozmieścić w tych lukach, aby jak najwięcej usunąć linii (jak w Tetrisie).
Nie wiem, jak rozpracować to optymalne rozmieszczenie figur, jak się odwołać, że akurat tu ma być ta figura, a jeżeli jest możliwość jej rozmieszczenia na kilka sposobów, to żeby program sprawdził, które rozmieszczenie jest najkorzystniejsze (rekurencja?). Później dla kolejnej figury trzeba zrobić to samo i dla kolejnej - czyli sprawdzić, który scenariusz rozmieszczenia figur będzie najoptymalniejszy.
Ktoś mógłby mi dać jakąś wskazówkę? Na razie myślałam nad grafami, że mogłoby to być to, zazwyczaj grafy wykorzystuje się do wyznaczania najkrótszej drogi i ma to pewien sens, ale nie wiem, jak to dalej pociągnąć.
Dzięki z góry za rady!

Comments

Zanim coś więcej powiem - skąd wziąłeś to zadanie?

---

Z konkursu programistycznego.

---

Bo matematycznie udowodniono (link, ale nie próbuj tego czytać), że maksymalizacja usuniętych linii w tetrisie to problem NP-kompletny - czyli, w uproszczeniu, nie ma algorytmu znajdującego optymalne rozwiązanie w rozsądnym czasie.

W konkursie chodziło o znalezienie idealnego rozwiązania, czy "w miarę dobrego, im lepszego tym więcej punktów"? Jeśli to pierwsze, to (o ile nie zauważyłem jakiegoś szczegółu upraszczającego to zadanie) dość dziwny dobór zadań ;)

W każdym razie...

Jakoś nie widzę opcji z grafem, bo błyskawicznie napęcznieje; ja bym zaczął ogólnie od jakiegoś naiwnego rozwiązania jako punkt wyjściowy i zastanawiał się dalej mając już coś działającego.

---

Dokładnie tu chodzi o to, ile maksymalnie można usunąć linii przy optymalnym rozkładzie nadchodzących klocków w sytuacji podanej na wejściu i to mam podać na wyjściu - ilość linii.
Mam przytoczyć całe zadanie? Generalnie, dla podanego przykładu udało mi się faktycznie, wyznaczyć optymalne rozwiązanie, ale to na kartce - w tym rzecz, że nie wiem, jak to "zautomatyzować".

O czym mniej więcej myślisz pisząc o naiwnym rozwiązaniu?

---

"naiwny" zazwyczaj oznacza "wariant prostszy i łatwiejszy do zaimplementowania, ale niekoniecznie optymalny".

Jeśli liczba klocków jest mała, to może faktycznie da się brute-force'm sprawdzić wszystkie opcje (tylko wycinając te kompletnie bez sensu).

Answer 1

Ja bym wyszedł od rozwiązania siłowego a później się zastanawiał...

Zacznij od maksymalizacji wypełnienia ostatniej linii, biorąc sekwencje które są permutacjami zbioru klocków.

A nieco prościej:

1. Wyzeruj ilość maksymalną linii.
2. Weź permutację klocków Tetris.
3. Weź pierwszy klocek wybranej permutacji.
4. Ułóż klocek tak aby zmaksymalizować wypełnienie ostatniej linii.
5. Usuń klocek z wygenerowanej permutacji
6. Jeśli są klocki, wróć do 3.
7. Zapisz ilość osiągniętych linii jeśli większa od bieżącej maksymalnej.
8. Jeśli jest następna permutacja wróć do 2.
9. Wypisz wynik.

Comments

1) Nie mogę wziąć permutacji nadchodzących klocków, bo mam je układać właśnie w zadanej kolejności - jest ona narzucona i basta.
2)  "4, Ułóż klocek tak aby zmaksymalizować wypełnienie ostatniej linii." - W jaki sposób? Jak to zautomatyzować? Jak mam wskazać, że skoro tu, tam i jeszcze gdzieś indziej jest miejsce, to ma wybrać jedno z tych kilku. A może ma sprawdzić wszystkie? No, ale właśnie - jak?

---

Ad 1. Ok. Tu nie masz wyjścia.

Ad 2. No to będziesz na początku siłowo przeglądał wszystkie kombinacje zrzucenia obróconego klocka. Oczywiście obroty także będą wszystkie. Czyli 2 pętle i notowanie wyniku w postaci skompletowanych linii. Jak? No po prostu napisać :-)

Jak więc zrozumiałem do siłowego rozwiązania pozostaje przejrzenie tych kombinacji. Jak to zrobisz, zauważysz że np. rozwiązanie w postaci budowania "drapacza chmur" czyli każdy klocek na innym, nie prowadzi do maksymalizacji wypełnionych linii. Dodasz warunek usunięcia takich kombinacji. Analogicznie dla kliku "nie stykających się drapaczy chmur".

Mi sprawdza się strategia: jak nie wiem jak zacząć, zaczynam od rozwiązania siłowego choćby po to by wiedzieć gdzie jest poziom rozwiązania najmniej optymalnego.

Tu napiszesz funkcje które i tak Ci się przydadzą (np. obrót klocka i detekcja minimalnej współrzędnej na której może leżeć).