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

https://ksp.sk/kucharka/bfs/

https://ksp.sk/kucharka/dfs/

https://ksp.sk/kucharka/halda/

https://ksp.sk/kucharka/dijkstra/

https://ksp.sk/kucharka/mriezky_implementacia/

In [ ]: