In [4]:
from queue import Queue
import pandas as pd
def zobraz_bludisko(data):
df = pd.DataFrame(data)
return df
pohyby = [ (0, -1), (0, 1), (-1, 0), (1, 0) ]
mapa = [['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.']]
n, m = len(mapa), len(mapa[0])
rS, sS = 6,2
rC, sC = 6,8
mapa[rS][sS] = 0
def da_sa(riadok, stlpec):
#vrati True, ak je dane policko prazdne/volne
#nemozeme ist na mriezka
return 0 <= riadok < n and 0 <= stlpec < m \
and mapa[riadok][stlpec] == '.'
rad = Queue()
rad.put( (rS, sS) )
while not rad.empty():
#vyberieme z radu a pridame susedov do radu
r, s = rad.get()
for smer_r, smer_s in pohyby:
novy_r, novy_s = r+smer_r, s+smer_s
if da_sa(novy_r, novy_s): #iba ak sa da na novu poziciu
mapa[novy_r][novy_s] = mapa[r][s]+1 #o jedno viac ako predtym
print(f'Vkladame: {novy_r}, {novy_s}')
rad.put( (novy_r, novy_s) )
zobraz_bludisko(mapa)
Vkladame: 6, 1 Vkladame: 6, 3 Vkladame: 5, 2 Vkladame: 7, 2 Vkladame: 6, 0 Vkladame: 5, 1 Vkladame: 7, 1 Vkladame: 6, 4 Vkladame: 5, 3 Vkladame: 7, 3 Vkladame: 4, 2 Vkladame: 5, 0 Vkladame: 7, 0 Vkladame: 4, 1 Vkladame: 6, 5 Vkladame: 7, 4 Vkladame: 4, 3 Vkladame: 3, 2 Vkladame: 4, 0 Vkladame: 3, 1 Vkladame: 5, 5 Vkladame: 7, 5 Vkladame: 3, 3 Vkladame: 2, 2 Vkladame: 3, 0 Vkladame: 2, 1 Vkladame: 4, 5 Vkladame: 2, 3 Vkladame: 1, 2 Vkladame: 2, 0 Vkladame: 1, 1 Vkladame: 3, 5 Vkladame: 1, 3 Vkladame: 0, 2 Vkladame: 1, 0 Vkladame: 0, 1 Vkladame: 3, 6 Vkladame: 2, 5 Vkladame: 1, 4 Vkladame: 0, 3 Vkladame: 0, 0 Vkladame: 3, 7 Vkladame: 2, 6 Vkladame: 1, 5 Vkladame: 0, 4 Vkladame: 3, 8 Vkladame: 2, 7 Vkladame: 4, 7 Vkladame: 1, 6 Vkladame: 0, 5 Vkladame: 3, 9 Vkladame: 2, 8 Vkladame: 4, 8 Vkladame: 1, 7 Vkladame: 5, 7 Vkladame: 0, 6 Vkladame: 3, 10 Vkladame: 2, 9 Vkladame: 4, 9 Vkladame: 1, 8 Vkladame: 5, 8 Vkladame: 0, 7 Vkladame: 6, 7 Vkladame: 2, 10 Vkladame: 4, 10 Vkladame: 1, 9 Vkladame: 5, 9 Vkladame: 0, 8 Vkladame: 6, 8 Vkladame: 7, 7 Vkladame: 1, 10 Vkladame: 5, 10 Vkladame: 0, 9 Vkladame: 6, 9 Vkladame: 7, 8 Vkladame: 0, 10 Vkladame: 6, 10 Vkladame: 7, 9 Vkladame: 7, 10
Out[4]:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 8 | 7 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 7 | 6 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 2 | 6 | 5 | 4 | 5 | # | 7 | 8 | 9 | 10 | 11 | 12 |
| 3 | 5 | 4 | 3 | 4 | # | 6 | 7 | 8 | 9 | 10 | 11 |
| 4 | 4 | 3 | 2 | 3 | # | 5 | # | 9 | 10 | 11 | 12 |
| 5 | 3 | 2 | 1 | 2 | # | 4 | # | 10 | 11 | 12 | 13 |
| 6 | 2 | 1 | 0 | 1 | 2 | 3 | # | 11 | 12 | 13 | 14 |
| 7 | 3 | 2 | 1 | 2 | 3 | 4 | # | 12 | 13 | 14 | 15 |
In [5]:
from queue import Queue
import pandas as pd
def zobraz_bludisko(data):
df = pd.DataFrame(data)
return df
pohyby = [ (0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1) ]
mapa = [['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.']]
n, m = len(mapa), len(mapa[0])
rS, sS = 6,2
rC, sC = 6,8
mapa[rS][sS] = 0
def da_sa(riadok, stlpec):
#vrati True, ak je dane policko prazdne/volne
#nemozeme ist na mriezka
return 0 <= riadok < n and 0 <= stlpec < m \
and mapa[riadok][stlpec] == '.'
rad = Queue()
rad.put( (rS, sS) )
while not rad.empty():
#vyberieme z radu a pridame susedov do radu
r, s = rad.get()
for smer_r, smer_s in pohyby:
novy_r, novy_s = r+smer_r, s+smer_s
if da_sa(novy_r, novy_s): #iba ak sa da na novu poziciu
mapa[novy_r][novy_s] = mapa[r][s]+1 #o jedno viac ako predtym
print(f'Vkladame: {novy_r}, {novy_s}')
rad.put( (novy_r, novy_s) )
zobraz_bludisko(mapa)
Vkladame: 6, 1 Vkladame: 6, 3 Vkladame: 5, 2 Vkladame: 7, 2 Vkladame: 5, 1 Vkladame: 5, 3 Vkladame: 7, 1 Vkladame: 7, 3 Vkladame: 6, 0 Vkladame: 5, 0 Vkladame: 7, 0 Vkladame: 6, 4 Vkladame: 7, 4 Vkladame: 4, 2 Vkladame: 4, 1 Vkladame: 4, 3 Vkladame: 4, 0 Vkladame: 6, 5 Vkladame: 5, 5 Vkladame: 7, 5 Vkladame: 3, 2 Vkladame: 3, 1 Vkladame: 3, 3 Vkladame: 3, 0 Vkladame: 4, 5 Vkladame: 2, 2 Vkladame: 2, 1 Vkladame: 2, 3 Vkladame: 2, 0 Vkladame: 3, 5 Vkladame: 3, 6 Vkladame: 1, 2 Vkladame: 1, 1 Vkladame: 1, 3 Vkladame: 1, 0 Vkladame: 1, 4 Vkladame: 2, 5 Vkladame: 2, 6 Vkladame: 3, 7 Vkladame: 2, 7 Vkladame: 4, 7 Vkladame: 0, 2 Vkladame: 0, 1 Vkladame: 0, 3 Vkladame: 0, 0 Vkladame: 0, 4 Vkladame: 1, 5 Vkladame: 0, 5 Vkladame: 1, 6 Vkladame: 1, 7 Vkladame: 3, 8 Vkladame: 2, 8 Vkladame: 4, 8 Vkladame: 1, 8 Vkladame: 5, 7 Vkladame: 5, 8 Vkladame: 0, 6 Vkladame: 0, 7 Vkladame: 0, 8 Vkladame: 3, 9 Vkladame: 2, 9 Vkladame: 4, 9 Vkladame: 1, 9 Vkladame: 5, 9 Vkladame: 0, 9 Vkladame: 6, 7 Vkladame: 6, 8 Vkladame: 6, 9 Vkladame: 3, 10 Vkladame: 2, 10 Vkladame: 4, 10 Vkladame: 1, 10 Vkladame: 5, 10 Vkladame: 0, 10 Vkladame: 6, 10 Vkladame: 7, 7 Vkladame: 7, 8 Vkladame: 7, 9 Vkladame: 7, 10
Out[5]:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 6 | 6 | 6 | 6 | 6 | 6 | 7 | 8 | 8 | 8 | 9 |
| 1 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 7 | 7 | 8 | 9 |
| 2 | 4 | 4 | 4 | 4 | # | 6 | 6 | 6 | 7 | 8 | 9 |
| 3 | 3 | 3 | 3 | 3 | # | 5 | 5 | 6 | 7 | 8 | 9 |
| 4 | 2 | 2 | 2 | 2 | # | 4 | # | 6 | 7 | 8 | 9 |
| 5 | 2 | 1 | 1 | 1 | # | 3 | # | 7 | 7 | 8 | 9 |
| 6 | 2 | 1 | 0 | 1 | 2 | 3 | # | 8 | 8 | 8 | 9 |
| 7 | 2 | 1 | 1 | 1 | 2 | 3 | # | 9 | 9 | 9 | 9 |
In [6]:
from queue import Queue
import pandas as pd
def zobraz_bludisko(data):
df = pd.DataFrame(data)
return df
pohyby = [ (2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2) ]
mapa = [['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.']]
n, m = len(mapa), len(mapa[0])
rS, sS = 6,2
rC, sC = 6,8
mapa[rS][sS] = 0
def da_sa(riadok, stlpec):
#vrati True, ak je dane policko prazdne/volne
#nemozeme ist na mriezka
return 0 <= riadok < n and 0 <= stlpec < m \
and mapa[riadok][stlpec] == '.'
rad = Queue()
rad.put( (rS, sS) )
while not rad.empty():
#vyberieme z radu a pridame susedov do radu
r, s = rad.get()
for smer_r, smer_s in pohyby:
novy_r, novy_s = r+smer_r, s+smer_s
if da_sa(novy_r, novy_s): #iba ak sa da na novu poziciu
mapa[novy_r][novy_s] = mapa[r][s]+1 #o jedno viac ako predtym
print(f'Vkladame: {novy_r}, {novy_s}')
rad.put( (novy_r, novy_s) )
zobraz_bludisko(mapa)
Vkladame: 4, 3 Vkladame: 4, 1 Vkladame: 7, 4 Vkladame: 7, 0 Vkladame: 5, 0 Vkladame: 6, 4 Vkladame: 2, 2 Vkladame: 5, 5 Vkladame: 3, 5 Vkladame: 5, 1 Vkladame: 3, 1 Vkladame: 6, 0 Vkladame: 2, 0 Vkladame: 5, 3 Vkladame: 3, 3 Vkladame: 7, 1 Vkladame: 4, 2 Vkladame: 4, 5 Vkladame: 7, 2 Vkladame: 5, 2 Vkladame: 0, 3 Vkladame: 0, 1 Vkladame: 1, 4 Vkladame: 3, 0 Vkladame: 1, 0 Vkladame: 3, 6 Vkladame: 6, 7 Vkladame: 4, 7 Vkladame: 6, 3 Vkladame: 1, 6 Vkladame: 2, 7 Vkladame: 2, 3 Vkladame: 3, 2 Vkladame: 1, 2 Vkladame: 6, 5 Vkladame: 6, 1 Vkladame: 2, 5 Vkladame: 2, 1 Vkladame: 2, 6 Vkladame: 5, 7 Vkladame: 3, 7 Vkladame: 7, 3 Vkladame: 4, 0 Vkladame: 1, 5 Vkladame: 1, 1 Vkladame: 1, 3 Vkladame: 0, 6 Vkladame: 0, 2 Vkladame: 1, 7 Vkladame: 4, 8 Vkladame: 2, 8 Vkladame: 7, 9 Vkladame: 5, 9 Vkladame: 7, 5 Vkladame: 6, 8 Vkladame: 3, 9 Vkladame: 0, 8 Vkladame: 0, 4 Vkladame: 1, 9 Vkladame: 0, 0 Vkladame: 7, 7 Vkladame: 0, 7 Vkladame: 0, 5 Vkladame: 3, 8 Vkladame: 1, 8 Vkladame: 7, 8 Vkladame: 6, 9 Vkladame: 4, 9 Vkladame: 5, 8 Vkladame: 2, 9 Vkladame: 0, 9 Vkladame: 5, 10 Vkladame: 3, 10 Vkladame: 1, 10 Vkladame: 7, 10 Vkladame: 4, 10 Vkladame: 2, 10 Vkladame: 0, 10 Vkladame: 6, 10
Out[6]:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 4 | 3 | 4 | 3 | 4 | 5 | 4 | 5 | 4 | 5 | 6 |
| 1 | 3 | 4 | 3 | 4 | 3 | 4 | 3 | 4 | 5 | 4 | 5 |
| 2 | 2 | 3 | 2 | 3 | # | 3 | 4 | 3 | 4 | 5 | 6 |
| 3 | 3 | 2 | 3 | 2 | # | 2 | 3 | 4 | 5 | 4 | 5 |
| 4 | 4 | 1 | 2 | 1 | # | 3 | # | 3 | 4 | 5 | 6 |
| 5 | 1 | 2 | 3 | 2 | # | 2 | # | 4 | 5 | 4 | 5 |
| 6 | 2 | 3 | 0 | 3 | 2 | 3 | # | 3 | 4 | 5 | 6 |
| 7 | 1 | 2 | 3 | 4 | 1 | 4 | # | 4 | 5 | 4 | 5 |
Dijskstra
Binárne vyhľadávacie stromy
(min-)Halda
In [ ]: