59 lines
3.0 KiB
Plaintext
59 lines
3.0 KiB
Plaintext
#def bfs(self, start:PoleKraty, cel:PoleKraty):
|
|
# sciezka = [start]
|
|
# wierzcholek_sciezka = [start, sciezka]
|
|
# bfs_kolejka = [wierzcholek_sciezka]
|
|
# odwiedzone = set()
|
|
# while bfs_kolejka:
|
|
# aktualne, sciezka = bfs_kolejka.pop(0)
|
|
# odwiedzone.add(aktualne)
|
|
# for neighbor in graph[aktualne]:
|
|
# if neighbor not in odwiedzone:
|
|
# if neighbor is cel:
|
|
# return sciezka + [neighbor]
|
|
# else:
|
|
# bfs_kolejka.append([neighbor, sciezka + [neighbor]])
|
|
def bfs(self, start: PoleKraty, cel: PoleKraty):
|
|
#sciezka = []
|
|
wierzcholek_sciezka = [["start",start], [["start",start]]]
|
|
bfs_kolejka = [wierzcholek_sciezka]
|
|
odwiedzone = set()
|
|
while bfs_kolejka:
|
|
#sciezka = []
|
|
elem=bfs_kolejka.pop(0)
|
|
odwA=str(elem[0][1].wiersz)+"/"+str(elem[0][1].kolumna)
|
|
odwiedzone.add(odwA)
|
|
polaObok=self.succ(elem[0][1])
|
|
for neighbor in polaObok:
|
|
sciezka=elem[1].copy()
|
|
sprOdw=str(neighbor[1].wiersz)+"/"+str(neighbor[1].kolumna)
|
|
if sprOdw not in odwiedzone:
|
|
if neighbor[1].wiersz==cel.wiersz and neighbor[1].kolumna==cel.kolumna:
|
|
sciezka.append(neighbor)
|
|
return sciezka
|
|
else:
|
|
sciezka.append([neighbor])
|
|
bfs_kolejka.append([neighbor, sciezka])
|
|
|
|
def succ(self, poleKraty: PoleKraty):
|
|
polaDostepneObok=list()
|
|
if poleKraty.kolumna-1>=0: #nie poza kratę
|
|
if self.krata.krata[poleKraty.wiersz][poleKraty.kolumna-1]!=ZawartoscPola.SCIANA: #nie szafka (szafka to ściana)
|
|
poleLewe=PoleKraty(self.krata, poleKraty.wiersz, poleKraty.kolumna-1)
|
|
naLewo=["Kierunek.LEWO", poleLewe]
|
|
polaDostepneObok.append(naLewo)
|
|
if poleKraty.wiersz - 1>= 0: # nie poza kratę
|
|
if self.krata.krata[poleKraty.wiersz-1][poleKraty.kolumna] != ZawartoscPola.SCIANA:
|
|
poleGorne = PoleKraty(self.krata, poleKraty.wiersz-1, poleKraty.kolumna)
|
|
naGore = ["Kierunek.GORA", poleGorne]
|
|
polaDostepneObok.append(naGore)
|
|
if poleKraty.kolumna+1<LICZBA_POL_W_POZIOMIE: #nie poza kratę
|
|
if self.krata.krata[poleKraty.wiersz][poleKraty.kolumna+1]!=ZawartoscPola.SCIANA:
|
|
polePrawe=PoleKraty(self.krata, poleKraty.wiersz, poleKraty.kolumna+1)
|
|
naPrawo = ["Kierunek.PRAWO", polePrawe]
|
|
polaDostepneObok.append(naPrawo)
|
|
if poleKraty.wiersz+1<LICZBA_POL_W_PIONIE: # nie poza kratę
|
|
if self.krata.krata[poleKraty.wiersz+1][poleKraty.kolumna] != ZawartoscPola.SCIANA:
|
|
poleDolne = PoleKraty(self.krata, poleKraty.wiersz+1, poleKraty.kolumna)
|
|
naDol = ["Kierunek.DOL", poleDolne]
|
|
polaDostepneObok.append(naDol)
|
|
return polaDostepneObok |