5. naloga

Tetris


Imamo ploščo, sestavljeno iz 8 × 8 kvadratnih polj, ki bi jo radi pokrili s ploščki v obliki raznih likov, podobnih tistim iz igre Tetris. Napiši program ali podprogram (funkcijo), ki bo ploščo v celoti pokril s ploščki, pri čemer se le-ti med seboj ne smejo prekrivati ali štrleti čez rob plošče. Na voljo so ploščki n različnih oblik, ki so oštevilčene od 1 do n; v vsaki obliki pa je na voljo le omejeno število ploščkov. Za delo s ploščki naj tvoj program uporablja naslednje funkcije (zanje torej predpostavi, da že obstajajo in ni mišljeno, da jih ti implementiraš sam):

  • int StOblik() — vrne n, torej število, ki pove, koliko različnih oblik ploščkov je na voljo.

  • int StPlosckov(int oblika) — vrne število razpoložljivih ploščkov oblike oblika. To je celo število, večje od 0, vanj pa so všteti tudi tisti ploščki, ki jih je tvoj program mogoče že postavil na ploščo.

  • bool JePokrito(int x, int y) — vrne logično vrednost, ki pove, ali je polje (x,y) na plošči trenutno pokrito (torej ali ga pokriva kakšen od že doslej postavljenih ploščkov). Na začetku izvajanja tvojega programa je plošča prazna (torej ni na njej še nobenega ploščka). Koordinate polj na plošči gredo od x = 0 (levo) do x = 7 (desno) in od y = 0 (zgoraj) do y = 7 (spodaj).

  • bool PreveriPloscek(int oblika, int x, int y) — vrne logično vrednost, ki pove, ali je mogoče na ploščo dodati plošček oblike oblika tako, da najbolj levo polje v najbolj zgornji vrstici tega ploščka pokrije polje (x,y) na plošči. (Funkcija preverja le obliko, ne pa tudi tega, ali imaš še na voljo kaj ploščkov te oblike ali pa si jih morda že vse postavil na ploščo.)

  • void PostaviPloscek(int oblika, int x, int y, bool b) — če je b == true, ta funkcija položi plošček oblike oblika na ploščo tako, da najbolj levo polje v najbolj zgornji vrstici tega ploščka pokrije polje (x, y) na plošči. Če je b == false, pa funkcija ta plošček s tega položaja odstrani.

Funkcija PostaviPloscek prekine izvajanje tvojega programa, če zahtevaš od nje operacijo, ki je ni mogoče izvesti (npr. dodajanje ploščka neke oblike, če si vse razpoložljive ploščke te oblike že položil na mrežo; ali dodajanje ploščka tako, da bi se prekrival z že obstoječimi ali štrlel čez rob mreže; ali brisanje ploščka, ki ga v resnici ni tam).

Ploščkov se pri tej nalogi ne dá obračati ali vrteti in funkciji PreveriPloscek in PostaviPloscek tega tudi ne poskušata početi. To pomeni, da štejeta na primer P1 in P2 za dve različni obliki in ploščkov ene oblike ne moremo zasukati in uporabiti kot ploščke druge oblike.

Primer. Recimo, da imamo ploščke naslednjih štirih oblik v naslednjih količinah:

6 ×
 6 ×
 4 ×
 2 ×

P01
P02


Potem lahko ploščo pokrijemo takole:



Še deklaracije gornjih funkcij v drugih jezikih:

{ V pascalu: }
function StOblik: integer;
function StPlosckov(oblika: integer): integer;
function JePokrito(x, y: integer): boolean;
function PreveriPloscek(oblika, x, y: integer): boolean;
procedure PostaviPloscek(oblika, x, y: integer; b: boolean);

// V javi: deklaracije so kot v besedilu naloge, le z boolean namesto bool.

# V pythonu:
def StOblik() -> int: . . .
def StPlosckov(oblika: int) -> int: . . .
def JePokrito(x: int, y: int) -> bool: . . .
def PreveriPloscek(oblika: int, x: int, y: int) -> bool: . . .
def PostaviPloscek(oblika: int, x: int, y: int, b: bool) -> None: . . .