#!/usr/bin/python3
# Hledání nejkratší cesty v bludišti
# Bludiště se načítá ze souboru "bludiste.in":
#    "." značí volná políčka
#    "#" jsou zdi
#    "0" je počáteční políčko
#    "$" je poklad, ke kterému chceme dojít
#    "*" zapíšeme na všechna políčka nejkratší cesty
#    "o" zapíšeme na ostatní prohledaná políčka

from collections import deque

class Bludiste:

    def __init__(self):
        self.bludiste = []
        self.radku = 0
        self.sloupcu = 0

    def nacti(self, soubor):
        with open(soubor) as f:
            for radek in f:
                self.bludiste.append(list(radek.strip()))
        self.radku = len(self.bludiste)
        self.sloupcu = len(self.bludiste[0])

    def vypis(self):
        for r in self.bludiste:
            print("".join(r))

    def najdi_start(self):
        for r in range(self.radku):
            for s in range(self.sloupcu):
                if self.bludiste[r][s] == '0':
                    return r, s
        raise RuntimeError("Jsem ztracen: bludiště nemá začátek!")

    def hledani_do_sirky(self, r, s):
        fronta = deque()
        fronta.append((r, s))
        self.bludiste[r][s] = 'o'
        self.odkud = [[None] * self.sloupcu for _ in range(self.radku)]
        konec = False

        def cesta(rr, ss):
            while self.odkud[rr][ss] is not None:
                rr, ss = self.odkud[rr][ss]
                self.bludiste[rr][ss] = '*'

        def soused(rr, ss):
            if 0 <= rr < self.radku and 0 <= ss < self.sloupcu:
                if self.bludiste[rr][ss] == '.':
                    self.bludiste[rr][ss] = 'o'
                    fronta.append((rr, ss))
                    self.odkud[rr][ss] = (r, s)
                elif self.bludiste[rr][ss] == '$':
                    self.odkud[rr][ss] = (r, s)
                    cesta(rr, ss)
                    nonlocal konec
                    konec = True

        while not konec and fronta:
            r, s = fronta.popleft()
            soused(r-1, s)
            soused(r+1, s)
            soused(r, s-1)
            soused(r, s+1)


b = Bludiste()
b.nacti("bludiste.in")
r0, s0 = b.najdi_start()
b.hledani_do_sirky(r0, s0)
b.vypis()