Tävlingsprogrammering/Uppgifter/Tetris
Tetris
Tetris är ett populärt datorspel som spelas i ett rutnät bestående av K kolumner och oändligt många rader. I varje drag släpps någon av följande sju bitar ner på spelplanen:
Innan en bit släpps kan spelaren rotera biten 90, 180 eller 270 grader och flytta den till vänster eller höger, så länge som hela biten befinner sig inom spelplanen. Biten faller sedan ner tills den når botten eller slår i någon upptagen ruta. I vår speciella version av Tetris får en bit bara släppas om det inte uppstår några "hål" i spelplanen. Med andra ord, efter att biten fallit får det inte någonstans finnas en tom ruta om rutan ovanför är fylld.
Betrakta följande exempel. Vi har en spelplan som är 6 kolumner bred och där höjderna är (antalet redan ifyllda rutor i varje kolumn) 2, 1, 1, 1, 0 och 1. Bit nummer 5 kan då släppas ner i spelplanen på fem olika sätt:
Skriv ett program som, givet höjderna för varje kolumn och biten som ska släppas, beräknar antalet olika sätt biten kan släppas. Dvs, antalet olika konfigurationer som spelplanen kan ha efter att biten har släppts.
Indata
Den första raden innehåller två heltal, K och P (1 ≤ K ≤ 100, 1 ≤ P ≤ 7), antalet kolumner och biten som ska släppas. Den andra raden innehåller K heltal, var och en mellan 0 och 100. De motsvarar den nuvarande höjden för varje kolumn.
Utdata
Skriv ut en rad med ett heltal, antalet olika sätt som biten kan släppas.
Exempel 1: Indata
6 5 2 1 1 1 0 1
Exempel 1: Utdata
5
Exempel 2: Indata
5 1 0 0 0 0 0
Exempel 2: Utdata
7
Exempel 3: Indata
9 4 4 3 5 4 6 5 7 6 6
Exempel 3: Utdata
1
Lösning
[redigera]Enklaste sättet att lösa uppgiften på är att lagra Tetrisbitarnas utseende i en array av någon form, i sina respektive rotationsformer. På så sätt slipper man skriva kod som roterar bitarna. Dessutom, eftersom det endast är konturerna av bitens undersida som avgör huruvida en bit kan placeras på ett visst ställe räcker det med att man lagra höjdskillnaderna i bitens undersida. För varje rotation för en bit loopar man sedan över möjliga x-koordinater, och kollar om bitens undersida har exakt samma höjddifferenser som indatat på de x-positionerna.