ITI0140:Ülesanne 15
Miinikits Miina tagasitulek
Teie ustav kits Miina on läinud kaduma. Kuulete häälte järgi, et ta on kadunud maa-alusesse labürinti. Kuna Miina aitas teid enne miini leidmisega, on aeg teil teda aidata. Peate koostama networkx-i graafi ala ASCII pildist ja leidma networkx-i abil lühima tee läbi selle graafi.
ASCII pildist tuleb lugeda välja koordinaadid nii, et iga sõlm koosneb suurest tähest ja numbrist. Täht tuleneb Rea numbrist, ja number tuleneb veeru numbrist, e. siis:
0 1 2 A [[' ', ' ', ' '], B ['X', 'X', ' '], C ['X', 'X', ' ']]
Peate realiseerima kaks funktsiooni:
def create_graph(labyrinth): Andes sisse ascii kaardi, nagu näiteks [[' ', ' ', ' '], ['X', 'X', ' '], ['X', 'X', ' ']]
, kus 'X' on sein ja ' ' (tühik) on tühimik, mida mööda saab liikuda, ülesandeks on koostada sellisest maatriksist networkx-i graafi, e. see funktsioon peaks tagastama vastava networkx-i graafi.
teiseks tuleb realiseerida järgnev:
def find_shortest_path(graph): See funktsioon peaks võtma sisse networkx-i graafi, ja tagastama tee A0-ist kõige all paremapoolsele sõlmele. Ehk eelmise näite järgi, peaks tagastama ['A0', 'A1', 'A2', 'B2', 'C2']. (Võib kasutada networkx-i lahendusi sellele)
On garanteeritud, et koridorid on maksimaalselt ühe ühiku laiused, ja et find_shortest_path-i testites antakse ette alati leitav tee.