vzdalenosti.py

#!/usr/bin/python3
# Výpočet vzdáleností 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
#    "o" zapíšeme na všechna dosažitelná 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 vypis_vzdalenost(self):
        for r in self.vzdalenost:
            vystup = []
            for d in r:
                if d is None:
                    vystup.append("---")
                else:
                    vystup.append("{:3d}".format(d))
            print(" ".join(vystup))

    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.vzdalenost = [[None] * self.sloupcu for _ in range(self.radku)]
        self.vzdalenost[r][s] = 0

        def soused(rr, ss, dd):
            if 0 <= rr < self.radku and \
               0 <= ss < self.sloupcu and \
               self.bludiste[rr][ss] == '.':
                self.bludiste[rr][ss] = 'o'
                self.vzdalenost[rr][ss] = dd
                fronta.append((rr, ss))

        while fronta:
            r, s = fronta.popleft()
            d = self.vzdalenost[r][s]
            soused(r-1, s, d+1)
            soused(r+1, s, d+1)
            soused(r, s-1, d+1)
            soused(r, s+1, d+1)


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