#!/usr/bin/python3 """ Vzorové řešení k úloze KSP 33-1-3 Laser v bludišti Autor Kristýna Petrlíková """ from enum import IntEnum from collections import deque class Direction(IntEnum): """ Označení jednotlivých směrů pomocí číselných konstant. Umožňuje přehlednější zápis při jejich používání. Tedy místo dir == 0 # pokud je směr nahoru se dá napsat dir == Direction.UP """ UP = 0 RIGHT = 1 DOWN = 2 LEFT = 3 class MazeObject: """ Třída reprezentující objekt v bludišti. _type: Typ objektu - Počáteční/koncové zrcadlo, klasické zrcadlo či stěna. Může nabývat znaků '0'-'7' nebo '#', 'Z' či 'C'. x, y: Souřadnice objektu. neighbours: Sousedé objektu (nejbližší objekty v daném směru). Přistupuje se k nim například takto: obj.neighbours[Direction.LEFT] # nejbližší soused vlevo needed_energy: Nejnižší možná energie potřebná k dostřelení paprsku do objektu. previous_mirror: Zrcadlo, které odrazilo paprsek na tento objekt. src_dir: Směr, ze kterého přichází paprsek. """ def __init__(self, _type, x, y): self._type = _type self.x = x self.y = y self.neighbours = [None] * 4 self.needed_energy = float("inf") # nekonečno self.previous_mirror = None self.src_dir = None # Načtení vstupu # Jelikož si ukládáme objekty do jednoho velkého pole, # rozměry bludiště jsou nám v podstatě k ničemu # (jinak bychom je mohli použít ke konstrukci 2D pole R x S). num_objects, num_rows, num_cols = map(int, input().split()) objects = [] start_object = None end_object = None # Načtení jednotlivých objektů for _ in range(num_objects): # Načtení trojice: typ, x-ová souřadnice, y-ová souřadnice _type, x, y = input().split() obj = MazeObject(_type, int(x), int(y)) objects.append(obj) # objekt je zdrojem laseru if _type == 'Z': start_object = obj # objekt je cílovým bodem laseru elif _type == 'C': end_object = obj # Vytvoříme graf reprezentovaný seznamem sousedů každého vrcholu. # Nejprve setřídíme objekty vzestupně (od nejmenšího k největšímu) # primárně podle jejich x-ových souřadnic, sekundárně podle y-ových. # Tedy pokud se x-ové souřadnice dvou objektů shodují, # pak se ve výsledku objeví dříve ten objekt, který měl # nižší y-ovou souřadnici (tj. ležel více vespod). # To nám umožní nalézt sousední objekty nacházející se nad sebou. objects.sort(key=lambda o: (o.x, o.y)) for i in range(num_objects-1): # Jestliže se objekty nachází ve stejném sloupci # (konkrétně i-tý objekt leží pod (i+1)-tým, # neboť díky setřízení musí mít nižší y-ovou souřadnici) # zapíšeme je vzájemně jako sousedy. # Zároveň nepotřebujeme vědět, že daný objekt sousedí se stěnou, # neboť na těch se v prohledávání stejně neúspěšně zastavíme. # (stačí je tedy v sousedech objektu reprezentovat # pomocí výchozí hodnoty None). if (objects[i].x == objects[i+1].x and objects[i]._type != '#' and objects[i+1]._type != '#'): objects[i].neighbours[Direction.UP] = objects[i+1] objects[i+1].neighbours[Direction.DOWN] = objects[i] # Objekty si setřídíme ještě jednou, tentokrát # primárně podle y-ových souřadnic, sekundárně podle x-ových. # To nám umožní nalézt sousedy ležící na stejném řádku. objects.sort(key=lambda o: (o.y, o.x)) for i in range(num_objects-1): if (objects[i].y == objects[i+1].y and objects[i]._type != '#' and objects[i+1]._type != '#'): objects[i].neighbours[Direction.RIGHT] = objects[i+1] objects[i+1].neighbours[Direction.LEFT] = objects[i] def get_next_dir(src_dir, mirror_dir): """ Vrací směr (↑↓,←→ ), který vznikne, pokud na zrcadlo natočené směrem mirror_dir přijde paprsek ze směru src_dir. Je třeba si pohlídat, aby paprsek nedopadal na odvrácenou stranu M̶ě̶s̶í̶c̶e̶ zrcadla, v tom případě se vrátí -1 pro neúspěch. Zároveň je k ničemu, když se paprsek odrazí stejným směrem, ze kterého přišel, takže tehdy odraz také nemá smysl. Směr paprsku budeme značit S. Paprskové a zrcadlové směry potřebujeme nějak sloučit, abychom s nimi mohli dále rozumně pracovat. Převedeme si tedy paprsek na zrcadlo, jehož odrazová plocha bude natočená ve směru tohoto paprsku (jinými slovy vynásobíme S dvěma). Tento nový směr si označíme S'. Původní směry: Převedené směry: Skutečné směry levých hran zrcadel: 0 0 1 2 3 ↑ ↖ ↑ ↗ ↖ ↑ ↗ 3 ← · → 1 6 ← · → 2 0 ← · → 4 ↓ ↙ ↓ ↘ ↙ ↓ ↘ 2 4 7 6 5 Paprsek může a) zrcadlem projít, přičemž nezmění směr b) natočit se doleva (S se zvýší o 3 (mod 4)) c) natočit se doprava (S se zvýší o 1 (mod 4)) a) Jestliže má být paprsek se zrcadlem rovnoběžný, musí být S' k zrcadlu kolmý, čili (2*src_dir - mirror_dir) % 8 == ± 2 => (2*src_dir - mirror_dir) % 4 == 2 b) Pokud má ze směru S vzniknout směr S+3 (mod 4), musí levá hrana zrcadla s paprskem svírat úhel 45°: mirror_dir == (2*src_dir + 5) % 8 c) Pokud má ze směru S vzniknout směr S+1 (mod 4), musí pravá hrana zrcadla s paprskem svírat úhel 45°: mirror_dir == (2*src_dir + 3) % 8 """ if (2*src_dir - mirror_dir) % 4 == 2: return src_dir if mirror_dir == (2*src_dir + 5) % 8: return (src_dir + 3) % 4 if mirror_dir == (2*src_dir + 3) % 8: return (src_dir + 1) % 4 return -1 # Vytvoříme si dvě fronty pro zjednodušenou verzi # Dijkstrova algoritmu: vzdálenosti mezi sousedními # vrcholy jsou vždy 0 nebo 1, díky čemuž # je algoritmus podobný prohledávání do šířky s tím rozdílem, # že do aktuální vlny můžeme přidávat i během jejího zpracování, # a pořád se nám to může vyplatit. class Query: """ Třída reprezentující prvek ve frontě. """ def __init__(self, src_object, target_object, src_dir, energy): self.src_object = src_object self.target_object = target_object self.src_dir = src_dir self.energy = energy curr_queue = deque() next_queue = deque() # Inicializace fronty přidáním jediného souseda zdroje laseru start_object.needed_energy = 0 curr_queue.append(Query(start_object, start_object.neighbours[Direction.UP], Direction.UP, 0)) found = False while not found: while curr_queue: # dokud fronta není prázdná query = curr_queue.popleft() # odebereme první objekt z fronty curr_obj = query.target_object src_dir = query.src_dir if (curr_obj is None or curr_obj.needed_energy < query.energy or (curr_obj._type != 'C' and curr_obj.needed_energy <= query.energy and (get_next_dir(query.src_dir, int(curr_obj._type)) == -1 or get_next_dir(curr_obj.src_dir, int(curr_obj._type)) != -1)) or curr_obj._type == 'Z'): # Objekt buďto neexistuje, nebo jeho dosažitelná energie # je už teď příliš nízká na to, abychom se snažili znovu ho použít. # Rovnost ceny energií připouštíme pouze # v případě, že paprsek se o dané zrcadlo # může odrazit bez nutnosti natočení, # a tedy tam, kam se odrazí, si polepšíme. # V tomto případě si také src_object chceme uložit # jako předchozí zrcadlo, protože směrům, # kam musíme otočit zrcadlo, je to jedno, # ale ve směru src_objectu bez otáčení na tom záleží. continue # zapíšeme výslednou energii a také zrcadlo, ze kterého se paprsek # na aktuální místo dostal curr_obj.needed_energy = query.energy curr_obj.src_dir = query.src_dir; curr_obj.previous_mirror = query.src_object if curr_obj._type == 'C': # Našli jsme, co jsme potřebovali. Můžeme skončit! found = True break # Paprsek pošleme dále... next_dir = get_next_dir(query.src_dir, int(curr_obj._type)) for d in range(4): # ...buď ve směru, v jakém by se normálně odrazil od zrcadla, # čímž se celková energie nezvýší if d == next_dir: curr_queue.append(Query(curr_obj, curr_obj.neighbours[d], d, query.energy)) # ...nebo jakkoliv jinak, ale budeme si muset muset připlatit else: next_queue.append(Query(curr_obj, curr_obj.neighbours[d], d, query.energy+1)) # Prohodíme fronty a začneme odznova curr_queue, next_queue = next_queue, curr_queue # Vypíšeme výslednou energii print(end_object.needed_energy) # Sledujeme trasu laseru od konce na začátek result = [] curr_mirror = end_object while curr_mirror != start_object: if curr_mirror != end_object: result.append(curr_mirror) curr_mirror = curr_mirror.previous_mirror # Vypíšeme pozice zrcadel tak, jak jsme je postupně navštěvovali # (v opačném pořadí, neboť jako poslední prvek jsme do výsledku # přidávali počáteční pozici) for mirror in reversed(result): print(mirror.x, mirror.y)