Depth First Search
¶modul queue
from queue import Queue, LifoQueue, PriorityQueue
def ads_test(ads): ads.put(3) ads.put(2) ads.put(7) while not ads.empty(): print(ads.get())
print('Zasobnik') ads_test(LifoQueue()) print('Rad') ads_test(Queue()) print('Prioritny rad') ads_test(PriorityQueue())
#n m
#zoznam hran, vrcholy cislovane od 1
14 14
1 2
2 6
2 7
3 5
4 5
4 6
6 7
7 8
8 9
8 10
11 12
11 13
12 14
13 14
#vrcholy si interne precislujeme od NULY
n, m = [ int(_) for _ in input().split() ]
susedia = [ [] for _ in range(n) ] #zoznam susedov pre kazdy vrchol
for _ in range(m):
x, y = [int(_)-1 for _ in input().split()] #ocislujeme od nuky
susedia[x].append(y)
susedia[y].append(x)
print(*susedia)
14 14 1 2 2 6 2 7 3 5 4 5 4 6 6 7 7 8 8 9 8 10 11 12 11 13 12 14 13 14 [1] [0, 5, 6] [4] [4, 5] [2, 3] [1, 3, 6] [1, 5, 7] [6, 8, 9] [7] [7] [11, 12] [10, 13] [10, 13] [11, 12]
for vrchol in range(n):
print(f'{vrchol}: {susedia[vrchol]}')
0: [1] 1: [0, 5, 6] 2: [4] 3: [4, 5] 4: [2, 3] 5: [1, 3, 6] 6: [1, 5, 7] 7: [6, 8, 9] 8: [7] 9: [7] 10: [11, 12] 11: [10, 13] 12: [10, 13] 13: [11, 12]
from graphviz import Graph
...
--------------------------------------------------------------------------- ModuleNotFoundError Traceback (most recent call last) ~\AppData\Local\Temp\ipykernel_15044\3188746648.py in <cell line: 1>() ----> 1 from graphviz import Graph ModuleNotFoundError: No module named 'graphviz'
for vrchol in range(n):
print(f'{vrchol}: {susedia[vrchol]}')
0: [1] 1: [0, 5, 6] 2: [4] 3: [4, 5] 4: [2, 3] 5: [1, 3, 6] 6: [1, 5, 7] 7: [6, 8, 9] 8: [7] 9: [7] 10: [11, 12] 11: [10, 13] 12: [10, 13] 13: [11, 12]
ocislovanie = [ None for _ in range(n)]
def dfs(vrchol):
rad = Queue()
rad.put( vrchol )
cislo = 0
while not rad.empty():
v = rad.get() #spracujeme dalsi vrchol, teda jeho susedov
ocislovanie[v] = cislo
print(f'vrchol {v} ma pridelene cislo {cislo}')
cislo += 1
#spracujeme susedov
for sused in susedia[v]:
if ocislovanie[sused] is None:
#ak novy/neocislovany/este nenavstiveny vrchol
rad.put(sused)
dfs(0)
print(ocislovanie)
#VIDIME, ze vrchol 6 je dvakrat (da sa prist k nemu z 1 aj z 5)
vrchol 0 ma pridelene cislo 0 vrchol 1 ma pridelene cislo 1 vrchol 5 ma pridelene cislo 2 vrchol 6 ma pridelene cislo 3 vrchol 3 ma pridelene cislo 4 vrchol 6 ma pridelene cislo 5 vrchol 7 ma pridelene cislo 6 vrchol 4 ma pridelene cislo 7 vrchol 7 ma pridelene cislo 8 vrchol 8 ma pridelene cislo 9 vrchol 9 ma pridelene cislo 10 vrchol 2 ma pridelene cislo 11 vrchol 8 ma pridelene cislo 12 vrchol 9 ma pridelene cislo 13 [0, 1, 11, 4, 7, 2, 5, 8, 12, 13, None, None, None, None]
ocislovanie = [ None for _ in range(n)]
def dfs(vrchol):
rad = Queue()
rad.put( vrchol )
cislo = 0
while not rad.empty():
v = rad.get() #spracujeme dalsi vrchol, teda jeho susedov
#spracujeme vrchol v, iba ak este neboli spracovane
if ocislovanie[v] is None:
ocislovanie[v] = cislo
print(f'vrchol {v} ma pridelene cislo {cislo}')
cislo += 1
#spracujeme susedov
for sused in susedia[v]:
if ocislovanie[sused] is None:
#ak novy/neocislovany/este nenavstiveny vrchol
rad.put(sused)
dfs(0)
print(ocislovanie)
vrchol 0 ma pridelene cislo 0 vrchol 1 ma pridelene cislo 1 vrchol 5 ma pridelene cislo 2 vrchol 6 ma pridelene cislo 3 vrchol 3 ma pridelene cislo 4 vrchol 7 ma pridelene cislo 5 vrchol 4 ma pridelene cislo 6 vrchol 8 ma pridelene cislo 7 vrchol 9 ma pridelene cislo 8 vrchol 2 ma pridelene cislo 9 [0, 1, 9, 4, 6, 2, 3, 5, 7, 8, None, None, None, None]
ocislovanie = [ None for _ in range(n)]
dfs(6)
print(ocislovanie)
vrchol 6 ma pridelene cislo 0 vrchol 1 ma pridelene cislo 1 vrchol 5 ma pridelene cislo 2 vrchol 7 ma pridelene cislo 3 vrchol 0 ma pridelene cislo 4 vrchol 3 ma pridelene cislo 5 vrchol 8 ma pridelene cislo 6 vrchol 9 ma pridelene cislo 7 vrchol 4 ma pridelene cislo 8 vrchol 2 ma pridelene cislo 9 [4, 1, 9, 5, 8, 2, 0, 3, 6, 7, None, None, None, None]
# vytvorenie komponentu:
def komponent(vrchol):
rad = Queue()
rad.put( vrchol )
navstiveny = [ False for _ in range(n)]
komponent = []
while not rad.empty():
v = rad.get() #spracujeme dalsi vrchol, teda jeho susedov
#spracujeme vrchol v, iba ak este neboli spracovane
if not navstiveny[v]:
navstiveny[v] = True
komponent.append(v)
#spracujeme susedov
for sused in susedia[v]:
if not navstiveny[sused]:
#ak novy/neocislovany/este nenavstiveny vrchol
rad.put(sused)
return(komponent)
komponent(0)
[0, 1, 5, 6, 3, 7, 4, 8, 9, 2]
komponent(6)
[6, 1, 5, 7, 0, 3, 8, 9, 4, 2]
komponent(10)
[10, 11, 12, 13]
def pocet_komponentov():
navstiveny = [ False for _ in range(n)]
pocet = 0
for vrchol in range(n):
if not navstiveny[vrchol]: #ak sme tam este neboli
#novy komponent z daneho vrhcholu
pocet += 1
#spustime prehladavanie zo vsetkych vrcholov
rad = Queue()
rad.put( vrchol )
while not rad.empty():
v = rad.get() #spracujeme dalsi vrchol, teda jeho susedov
#spracujeme vrchol v, iba ak este neboli spracovane
if not navstiveny[v]:
navstiveny[v] = True
#spracujeme susedov
for sused in susedia[v]:
if not navstiveny[sused]:
#ak novy/neocislovany/este nenavstiveny vrchol
rad.put(sused)
return pocet
pocet_komponentov()
2
namiesto radu pouzijeme zasobnik
# vytvorenie komponentu:
def komponent(vrchol):
rad = LifoQueue()
rad.put( vrchol )
navstiveny = [ False for _ in range(n)]
komponent = []
while not rad.empty():
v = rad.get() #spracujeme dalsi vrchol, teda jeho susedov
#spracujeme vrchol v, iba ak este neboli spracovane
if not navstiveny[v]:
navstiveny[v] = True
komponent.append(v)
#spracujeme susedov
for sused in susedia[v]:
if not navstiveny[sused]:
#ak novy/neocislovany/este nenavstiveny vrchol
rad.put(sused)
return(komponent)
komponent(0)
[0, 1, 6, 7, 9, 8, 5, 3, 4, 2]
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
n, m = len(mapa), len(mapa[0])
rS, sS = 6,2 #riadok a stlpec Startu
rC, sC = 6,8 #... Ciela
mapa
[['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'], ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.']]
for riadok in mapa:
print(*riadok)
. . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . # . . . . . . . . . . # . # . . . . . . . . # . # . . . . . . . . . . # . . . . . . . . . . # . . . .
for riadok in mapa:
print(*riadok, sep='')
........... ........... ....#...... ....#...... ....#.#.... ....#.#.... ......#.... ......#....
mapa[rS][sS] = 'S'
for riadok in mapa:
print(*riadok, sep='')
........... ........... ....#...... ....#...... ....#.#.... ....#.#.... ..S...#.... ......#....
pohyby = [ (-1, 0), (0, 1), (1, 0), (0, -1) ] #hore, vpravo, dole, vlavo
for pohyb in pohyby:
print(rS+pohyb[0], sS+pohyb[1])
5 2 6 3 7 2 6 1
for zmena_r, zmena_s in pohyby:
print(rS+zmena_r, sS+zmena_s)
5 2 6 3 7 2 6 1
r, s = 6, 4
for zmena_r, zmena_s in pohyby:
print(r+zmena_r, s+zmena_s)
5 4 6 5 7 4 6 3
def da_sa(riadok, stlpec):
return mapa[riadok][stlpec] != '#'
r, s = 6, 4
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
6 5 7 4 6 3
r, s = 6, 0
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
5 0 6 1 7 0 6 -1
Musíme kontrolovať, aj či nie sme mimo mapy:
def da_sa(riadok, stlpec):
if stlpec < 0 or stlpec >= len(mapa[0]) :
return False
return mapa[riadok][stlpec] != '#'
r, s = 6, 10
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
5 10 7 10 6 9
def da_sa(riadok, stlpec):
if stlpec < 0 or stlpec >= len(mapa[0]) :
return False
#dalsi if pre riadok
return mapa[riadok][stlpec] != '#'
r, s = 6, 10
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
def da_sa(riadok, stlpec):
return 0 <= riadok < n \
and 0 <= stlpec < m \
and mapa[riadok][stlpec] != '#'
r, s = 6, 10
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
5 10 7 10 6 9
import pandas as pd
def zobraz_bludisko(data):
df = pd.DataFrame(data)
df = df.style.applymap(lambda val: f'color: {"red" if val=="#" else "blue" if val=="?" else "black"}')
return df
zobraz_bludisko(mapa)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | . | . | . | # | . | # | . | . | . | . |
6 | . | . | S | . | . | . | # | . | . | . | . |
7 | . | . | . | . | . | . | # | . | . | . | . |
r, s = 6, 2
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 1
zobraz_bludisko(mapa)
5 2 6 3 7 2 6 1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | . | 1 | . | # | . | # | . | . | . | . |
6 | . | 1 | S | 1 | . | . | # | . | . | . | . |
7 | . | . | 1 | . | . | . | # | . | . | . | . |
r, s = 6, 1
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 2
zobraz_bludisko(mapa)
5 1 6 2 7 1 6 0
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | 2 | 1 | . | # | . | # | . | . | . | . |
6 | 2 | 1 | 2 | 1 | . | . | # | . | . | . | . |
7 | . | 2 | 1 | . | . | . | # | . | . | . | . |
Prepisali sme si start (nula krokov), kontrolu da_sa musime upravit
def da_sa(riadok, stlpec):
return 0 <= riadok < n \
and 0 <= stlpec < m \
and mapa[riadok][stlpec] == '.'
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
mapa[rS][sS] = 0
r, s = 6, 2
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 1
zobraz_bludisko(mapa)
5 2 6 3 7 2 6 1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | . | 1 | . | # | . | # | . | . | . | . |
6 | . | 1 | 0 | 1 | . | . | # | . | . | . | . |
7 | . | . | 1 | . | . | . | # | . | . | . | . |
r, s = 6, 1
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 2
zobraz_bludisko(mapa)
5 1 7 1 6 0
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | 2 | 1 | . | # | . | # | . | . | . | . |
6 | 2 | 1 | 0 | 1 | . | . | # | . | . | . | . |
7 | . | 2 | 1 | . | . | . | # | . | . | . | . |
r, s = 5, 2
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 2
zobraz_bludisko(mapa)
4 2 5 3
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | 2 | . | # | . | # | . | . | . | . |
5 | . | 2 | 1 | 2 | # | . | # | . | . | . | . |
6 | 2 | 1 | 0 | 1 | . | . | # | . | . | . | . |
7 | . | 2 | 1 | . | . | . | # | . | . | . | . |
r, s = 6, 3
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = 2
zobraz_bludisko(mapa)
6 4 7 3
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | 2 | . | # | . | # | . | . | . | . |
5 | . | 2 | 1 | 2 | # | . | # | . | . | . | . |
6 | 2 | 1 | 0 | 1 | 2 | . | # | . | . | . | . |
7 | . | 2 | 1 | 2 | . | . | # | . | . | . | . |
r, s = 4, 2
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
3 2 4 3 4 1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | 3 | . | # | . | . | . | . | . | . |
4 | . | 3 | 2 | 3 | # | . | # | . | . | . | . |
5 | . | 2 | 1 | 2 | # | . | # | . | . | . | . |
6 | 2 | 1 | 0 | 1 | 2 | . | # | . | . | . | . |
7 | . | 2 | 1 | 2 | . | . | # | . | . | . | . |
Vidime, ze potrebujeme pridavat do radu policka teda dvojice (r,s)
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rad = Queue()
rad.put( (rS, sS) )
mapa[rS][sS] = 0
while not rad.empty():
r, s = rad.get()
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
print(novy_r, novy_s)
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
5 2 6 3 7 2 6 1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | . | . | . | . | . | . | . | . | . | . | . |
1 | . | . | . | . | . | . | . | . | . | . | . |
2 | . | . | . | . | # | . | . | . | . | . | . |
3 | . | . | . | . | # | . | . | . | . | . | . |
4 | . | . | . | . | # | . | # | . | . | . | . |
5 | . | . | 1 | . | # | . | # | . | . | . | . |
6 | . | 1 | 0 | 1 | . | . | # | . | . | . | . |
7 | . | . | 1 | . | . | . | # | . | . | . | . |
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rad = Queue()
rad.put( (rS, sS) )
mapa[rS][sS] = 0
while not rad.empty():
r, s = rad.get()
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
rad.put( (novy_r, novy_s) )
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
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 |
mapa[rC][sC]
12
Do hlbky fungovat NEBUDE!!
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rad = LifoQueue()
rad.put( (rS, sS) )
mapa[rS][sS] = 0
while not rad.empty():
r, s = rad.get()
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
rad.put( (novy_r, novy_s) )
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 14 | 15 | 16 | 17 | 18 | 19 | 44 | 43 | 42 | 41 | 40 |
1 | 13 | 12 | 11 | 10 | 19 | 20 | 21 | 42 | 41 | 40 | 39 |
2 | 12 | 11 | 10 | 9 | # | 21 | 22 | 25 | 42 | 37 | 38 |
3 | 5 | 6 | 7 | 8 | # | 22 | 23 | 24 | 25 | 36 | 37 |
4 | 4 | 5 | 6 | 7 | # | 23 | # | 25 | 26 | 35 | 34 |
5 | 3 | 2 | 1 | 8 | # | 24 | # | 26 | 27 | 34 | 33 |
6 | 2 | 1 | 0 | 1 | 26 | 25 | # | 27 | 28 | 31 | 32 |
7 | 3 | 2 | 1 | 28 | 27 | 26 | # | 28 | 29 | 30 | 31 |
Osesmerový pohyb
pohyby = [ (-1, 0), (0, 1), (1, 0), (0, -1),
(-1, -1), (-1, 1), (1, -1), (1, 1) ] #hore, vpravo, dole, vlavo
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rad = Queue()
rad.put( (rS, sS) )
mapa[rS][sS] = 0
while not rad.empty():
r, s = rad.get()
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
rad.put( (novy_r, novy_s) )
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
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 |
pohyby = [ (2, 1), (2, -1), (-2, 1), (-2, -1),
(1, 2), (1, -2), (-1, 2), (-1, -2),]
mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rad = Queue()
rad.put( (rS, sS) )
mapa[rS][sS] = 0
while not rad.empty():
r, s = rad.get()
for zmena_r, zmena_s in pohyby:
novy_r, novy_s = r+zmena_r, s+zmena_s
if da_sa(novy_r, novy_s): #iba ak je dane policko volne/nie je prekazka
rad.put( (novy_r, novy_s) )
mapa[novy_r][novy_s] = mapa[r][s]+1
zobraz_bludisko(mapa)
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 |