7. tréningové zadanie - skúška z 19.6.2017

Do veľkého skladu kúpili upratovací robot, ktorý je schopný prejsť nejakú zadanú trasu a pri každom kroku vyčistiť plochu veľkosti 1x1. Počas jeho čistiacej trasy nechceme, aby stúpil na už vyčistenú plochu a požadujeme, aby sa na koniec vrátil na svoje štartové pole, kde sa nachádza jeho nabíjacia stanica (zrejme túto štartovaciu plochu nečistí). Ak si predstavíte veľký sklad ako štvorcovú sieť, ktorého políčka sú veľkosti 1x1, robot sa môže presúvať len na susedné políčka, ktoré majú spoločnú jednu stranu. Na niektorých políčkach môžu byť pre robota prekážky a zrejme na tieto vojsť nemôže.

Napíšte program, ktorý pre robota navrhne takú čo najdlhšiu trasu, ktorá začína na vopred zadanom políčku (a teda na ňom aj končí). Celý sklad reprezentujte ako neorientovaný neohodnotený graf, v ktorom vrcholy sú prázdne políčka štvorcovej siete a hranami sú spojené tie vrcholy, ktorých políčka majú spoločné hrany. Políčka s prekážkami nie sú vrcholmi grafu.

Zadefinujte triedu Graf:

class Graf:
    def __init__(self, meno_suboru):
        self.g = {}                   # reprezentácia grafu
        ...

    def vrcholy(self):
        return []

    def hrana(self, v1, v2):
        return False

    def start(self, riadok, stlpec):
        return 0, []

kde

  • metóda __init__(self, meno_suboru): prečíta súbor a vytvorí z neho neorientovaný neohodnotený graf; realizujte ho ako asociatívne pole množín súsedov, kde kľúčmi sú všetky vrcholy (dvojice čísel pre riadok a stĺpec) a hodnotami pre tieto vrcholy sú množiny susediacich vrcholov, t.j. množiny dvojíc čísel pre riadok a stĺpec;

  • metóda vrcholy(self): vráti zoznam všetkých vrcholov grafu, t.j. zoznam dvojíc (tuple) čísel pre riadok a stĺpec;

  • metóda hrana(self, v1, v2): zistí, či je hrana medzi vrcholmi grafu v1 a v2, metóda vráti True alebo False;

  • metóda start(self, riadok stlpec): pomocou backtrackingu nájde ľubovoľnú maximálne dlhú trasu, ktorá začína v zadanom vrchole, prejde cez maximálny počet vrcholov práve raz a skončí v štartovom vrchole (tento už do cesty nevkladajte); metóda vráti dvojicu: počet rôznych maximálne dlhých trás a ľubovoľnú z nich ako zoznam (typu list) dvojíc čísel pre riadok a stĺpec; ak takáto cesta neexistuje, metóda vráti dvojicu 0, [].

Sklad je zadaný v súbore takto:

  • v každom riadku je popísaný jeden riadok štvorcovej siete - všetky radky sú rovnako dlhé;

  • každý znak reprezentuje jedno políčko: ak je to znak bodka '.', označuje to prázdne políčko, inak je to políčko s prekážkou

Napr. pre takéto zadanie grafu:

x...
...x
....

takýto test:

if __name__ == '__main__':
    g = Graf('subor1.txt')
    print('vrcholy =', g.vrcholy())
    for v1, v2 in ((0,0),(0,1)), ((1,0),(0,1)), ((1,0),(1,1)):
        print('hrana', v1, v2, g.hrana(v1, v2))
    print('cesta', (0, 0), g.start(0, 0))
    print('cesta', (1, 1), g.start(1, 1))

vypíše napr.:

vrcholy = [(0, 1), (1, 2), (2, 3), (2, 0), (1, 0), (0, 3), (2, 2), (1, 1), (2, 1), (0, 2)]
hrana (0, 0) (0, 1) False
hrana (1, 0) (0, 1) False
hrana (1, 0) (1, 1) True
cesta (0, 0) (0, [])
cesta (1, 1) (2, [(1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)])

Z úlohového servera L.I.S.T. si stiahnite kostru programu skuska.py. Mali by ste dodržať tieto vlastnosti programu:

  • Nemeňte mená už zadaných atribútov (metód).

  • Do existujúcej triedy môžete pridávať vlastné atribúty a metódy, nepoužívajte ale atribúty, v ktorých si budete uchovávať pôvodný dvojrozmerný zoznam.

  • Pri testovaní vášho riešenia sa bude kontrolovať aj štruktúra vami vytvoreného grafu.

Aby ste mohli spúšťať skúškové testy, riešenie (bez ďalších súborov) odovzdajte na úlohový server https://list.fmph.uniba.sk/. Testy postupne na všetkých testovacích súboroch preverujú vlastnosti vašich algoritmov, pri prvej chybe sa testovanie s daným súborom preruší a ďalšie časti sa netestujú:

  • 40% bodov za vytvorenie grafu

  • 40% bodov za algoritmus hľadania maximálnej trasy

  • 20% bodov za správny počet maximálnych trás

  • pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač