Zadanie skúšky 14.1.2015
Indiáni v labyrinte
Keď sa indián dostane do labyrintu, tak samostatne postupuje, kým má kam. Každé prejdené políčko
pritom označí značkou, že tu už bol a teda takto označené políčko je už neskôr nepriechodné. Lenže
indián postupuje samostatne len pokým je jeho cesta jednoznačná, t.j. ak stojí na políčku, z ktorého
je viac možností, kam sa vybrať, tak tu skončí (na tomto políčku zostane stáť). Vtedy môžeme na nejaké iné voľné políčko umiestniť ďalšieho indiána a ten opäť postupuje samostatne, kým je jeho cesta
jednoznačná. Takto môže niekoľko indiánov označiť hoci aj všetky políčka labyrintu. Zrejme, ak indiána umiestnime na políčko, ktoré má viac ako jednu možnosť, kam sa dá pokračovať, indián toto jedno
políčko označí značkou a na ňom aj zastane.
Vašou úlohou je prečítať textový súbor s popisom labyrintu a potom postupne podľa ďalších pokynov
umiestňovať niekoľko indiánov a pritom sledovať, ako sa označujú políčka. Program na požiadanie
oznámi počet voľných políčok, počet políčok označených značkami, prípadne pozície všetkých indiánov.
Riešenie zapíšte do triedy Program s týmito metódami:
class Program:
def __init__(self, meno_suboru):
...
def indian(self, riadok, stlpec):
...
def pocet_znaciek(self):
...
def pocet_volnych(self):
...
def vsetci_indiani(self):
...
Kde metódy:




indian(self, riadok, stlpec): umiestni na dané políčko indiána a realizuje jeho samostatný
prechod labyrintom aj s označovaním políčok; ak je toto políčko už označené, alebo je to prekážka, indián sa neumiestni a tento príkaz sa ignoruje
pocet_znaciek(self): vráti momentálny počet označených políčok
pocet_volnych(self): vráti momentálny počet voľných políčok
vsetci_indiani(self): vráti pole (typ list) pozícií všetkých indiánov v labyrinte, pričom pozície
sú dvojice (riadok,stĺpec)
Textový súbor obsahuje popis labyrintu (štvorcová sieť) v tvare:


prvý riadok obsahuje 2 čísla: počet riadkov a počet stĺpcov labyrintu
všetky ďalšie riadky súboru obsahujú štvorice čísel, ktoré popisujú jeden blok prekážok, t.j.
obdĺžnik obsadených políčok v tvare: riadok stĺpec počet_riadkov počet_stĺpcov
kde riadok, stĺpec (číslujeme od 0) je pozícia ľavého horného políčka a ďalšie dve čísla sú veľkosť takéhoto bloku, napr. 2 1 3 5 označuje blok 15 nepriechodných políčok, pričom začína v
2. riadku a 1. stĺpci
Napr. pre súbor
5 5
1 1 3 3
2 0 3 2
labyrint má takýto tvar:
.
.
x
x
x
.
x
x
x
x
.
x
x
x
.
.
x
x
x
.
.
.
.
.
.
Ak umiestnime prvého indiána na políčko (1,0), tak označí všetky voľné políčka a zastane na políčku
(4,2). Metóda pocet_znaciek() vráti číslo 12, metóda vsetci_indiani() vráti jednoprvkové pole s pozíciou indiána, teda [(4,2)].
Ak by sme ale indiána umiestnili na políčko, napr. (0,3), ten by toto jedno políčko označil a, keďže sa
nevie rozhodnúť, kadiaľ má pokračovať, tak tu zastane. Ak by sme teraz zisťovali pocet_znaciek(),
dostali by sme číslo 1. Ďalších dvoch indiánov by sme mohli položiť napr. na pozície (0,2) a (4,2). Každý z nich by označkoval svoju časť labyrintu. Metóda pocet_znaciek() by teraz vrátila číslo 12, a metóda vsetci_indiani() vráti ich pozície, napr. [(0,3),(1,0),(0,4)]. Na poradí pozícií indiánov nezáleží.
Program môžete testovať napr. takto:
if __name__ == '__main__':
sk = Program('subor1.txt')
print('pocet volnych =', sk.pocet_volnych())
sk.indian(0,3)
print('pocet znaciek =', sk.pocet_znaciek())
print('pozicie indianov =', sk.vsetci_indiani())
sk.indian(0,2)
sk.indian(4,2)
print('pocet znaciek =', sk.pocet_znaciek())
print('pozicie indianov =', sk.vsetci_indiani())
mal by vypísať:
pocet volnych = 12
pocet znaciek = 1
pozicie indianov = [(0, 3)]
pocet znaciek = 12
pozicie indianov = [(0, 3), (0, 4), (1, 0)]
Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py. Riešenie (bez dátových
súborov) odovzdajte na úlohový server http://capek.ii.fmph.uniba.sk/list.
Skúška pokračuje od 12:00 vyhodnotením v kancelárii m162.
Download

1. riadny termín skúšky