#!/usr/bin/python3 import sys # Možné směry, očíslované po směru hodinových ručiček dirs = [ (0, -1, "L"), # 0 = doleva (-1, 0, "N"), # 1 = nahoru (0, +1, "P"), # 2 = doprava (+1, 0, "D") # 3 = dolů ] def read_input(): """Načte vstupní soubor a vrátí 2D seznam obsahující bludiště.""" output = [] for line in sys.stdin: output.append(list(line.strip())) output.pop(0) if not output[-1]: output = output[:-1] return output def find_player(): """Vrátí souřadnice počáteční polohy hráče v bludišti.""" for y in range(len(maze)): for x in range(len(maze[0])): if maze[y][x] == "P": return y, x def reverse_dir(dir): """Vrátí směr otočený 180 stupňů.""" return (dir + 2) % 4 def perpendicular_dirs(dir): """Vrátí dvojici směrů kolmých na zadaný směr.""" return (dir + 1) % 4, (dir + 3) % 4 def dir_cmd(dir): """Vrátí příkaz pro pohyb v daném směru.""" return dirs[dir][2] def move(yx, dir): """Vrátí pozici, která se nachází od zadané pozice jedno políčko ve směru dir.""" return yx[0] + dirs[dir][0], yx[1] + dirs[dir][1] def get(yx): """Vrátí druh políčka na dané pozici. Mimo bludiště si domýšlí zdi. """ if 0 <= yx[0] < len(maze) and 0 <= yx[1] < len(maze[0]): return maze[yx[0]][yx[1]] else: return "#" def set(yx, mark): """Změní druh políčka na souřadnicích yx; pomocí "O" si DFS značí, kde už bylo pole prohledáno.""" maze[yx[0]][yx[1]] = mark def is_free(yx): """Vratí True, pokud je políčko na yx průchozí.""" return get(yx) not in "#*" def out(command): """Vypíše na výstup jeden nebo více příkazů.""" print(command, end="") def find_shelter(bomb_yx): """Najde úkryt pro odpálení bomby na zadané pozici. Vrací směr rovně, počet kroků a směr do boku.""" for dir in range(4): yx = bomb_yx step_count = 0 while is_free(move(yx, dir)): yx = move(yx, dir) step_count += 1 for pd in perpendicular_dirs(dir): if is_free(move(yx, pd)): return dir, step_count, pd return -1, -1, -1 def bombing(straight_dir, straight_steps, side_dir): """Zařídí umístění bomby, cestu do úkrytu, odpálení a návrat z úkrytu zpět.""" out("B") out(straight_steps * dir_cmd(straight_dir)) out(dir_cmd(side_dir)) out("O") out(dir_cmd(reverse_dir(side_dir))) out(straight_steps * dir_cmd(reverse_dir(straight_dir))) def solve(player_yx): """Hlavní prohledávání do hloubky.""" set(player_yx, "O") for dir in range(4): yx = move(player_yx, dir) if get(yx) == "*": sh_straight_dir, sh_straight_steps, sh_side_dir = find_shelter(player_yx) if sh_straight_dir >= 0: bombing(sh_straight_dir, sh_straight_steps, sh_side_dir) else: # Speciální případ diskutovaný ve vzorovém řešení out(dir_cmd(reverse_dir(dir))) sh_straight_dir, sh_straight_steps, sh_side_dir, = find_shelter(move(player_yx, reverse_dir(dir))) assert sh_straight_dir >= 0 bombing(sh_straight_dir, sh_straight_steps, sh_side_dir) out(dir_cmd(dir)) set(yx, ".") if get(yx) == ".": out(dir_cmd(dir)) solve(yx) out(dir_cmd(reverse_dir(dir))) sys.setrecursionlimit(10000) # Zvýšíme maximální povolenou hloubku rekurze maze = read_input() solve(find_player())