Zkouška Pergel 23.6. 2020

Krychličky

Prostorový útvar je složený z jednotkových krychliček a chceme spočítat, kolika různými způsoby ho lze rozdělit na dvě souvislé části.
Přitom:

krychličky, ze kterých se útvar skládá, na sebe přiléhají stěnami
útvar není větší než krychle rozměru 3x3x3 krychličky
obě části musí být složeny z celých jednotkových krychliček
souvislost je definovaná takto:

• jednotková krychlička je souvislá část

• spojením dvou disjunktních souvislých částí tak, že se
  přinejmenším jedna jednotková krychlička z jedné části a
  jedna jednotková krychlička z druhé části spojí některými
  svými stěnami, vznikne také souvislá část
  můžeme předpokládat, že jednotkové krychličky jsou očíslovány, takže řešení, které se liší jen pootočením považujeme za různá řešení
  části naopak nebudou nijak pojmenované, takže je jedno, která část je první a která druhá
  dvě části, na které původní útvar rozdělíme, nemusí být oddělitelné, tedy například rozdělení, při kterém je jedna část pouze jednotkovou krychličkou ve středu krychle 3x3x3 a druhá část je zbytek této krychle, je přijatelné a budeme ho započítávat

Zadání

Navrhněte program, který zjistí, kolika způsoby lze zadaný prostorový útvar rozdělit na dvě souvislé části.
Vstup
Vstupem programu je seznam krychliček, ze kterých se útvar skládá,
každá krychlička je zadaná pomocí souřadnic svého levého horního
roku, například:

000 100 010 110

Výstupem je číslo udávající počet možností, například:

6

(Vysvětlení: útvar popsaný vstupem sestává ze čtyř krychliček uspořádaných do čtverce 2x2, na dvě části ho můžeme rozdělit buď tak, že jedna část bude jedna krychlička a druhá část tři krychličky (4 možnosti) nebo tak, že jedna část budou dvě krychličky vedle sebe (2 možnosti).)
V odpovědi popište
1) postřehy
2) zdůvodněnou volbu algoritmu
3) representaci dat
4) dekompozici programu
5) diskusi
, v případě potřeby i 0) upřesnění zadání.
Počty velikosti
 paměť 500MB