Kedves Diákjaim, aki ezt is megoldja az már igazi profi, mert tudása az enyémmel vetekedik, ez a feladat az érettségin előforduló legbonyolultabb algoritmusokat (rekurzió, mátrixok, szótárak) ötvözi. Kiválóan fejleszti a logikai gondolkodást és a kódhatékonysági szemléletet.Feladat: Útvonal optimalizálás és statisztika labirintusbanEgy N × N-es labirintusban a karaktered egy mátrix bal felső sarkából (0,0) indul, és a cél a jobb alsó sarok (N-1, N-1).
A feladat:Határozd meg a lehetséges összes útvonalat, amellyel a célba lehet érni (csak jobbra és lefelé léphetsz). Válaszd ki a legrövidebb útvonalat. Számold ki a lépések hatékonyságát és tárold el a megtett koordinátákat. Aki ezt az algoritmust is megérti az nálam már királynak számít.
----------
def osszes_utvonal(matrix, x, y, cel_x, cel_y, aktualis_ut, talalatok):
if x > cel_x or y > cel_y:
return
if matrix[x][y] == 1:
return
aktualis_ut.append((x, y))
if x == cel_x and y == cel_y:
talalatok.append(list(aktualis_ut))
else:
osszes_utvonal(matrix, x + 1, y, cel_x, cel_y, aktualis_ut, talalatok)
osszes_utvonal(matrix, x, y + 1, cel_x, cel_y, aktualis_ut, talalatok)
aktualis_ut.pop()
def utvonal_statisztika(utvonalak):
if not utvonalak:
return "Nincs érvényes útvonal."
legrovidebb = min(utvonalak, key=len)
iranyok = []
for i in range(len(legrovidebb) - 1):
x1, y1 = legrovidebb[i]
x2, y2 = legrovidebb[i + 1]
if x2 > x1:
iranyok.append("Lefelé")
elif y2 > y1:
iranyok.append("Jobbra")
return {
"ossz_utvonal_szam": len(utvonalak),
"legrovidebb_ut_hossza": len(legrovidebb) - 1,
"legrovidebb_ut_koordinatak": legrovidebb,
"lepések_iranya": iranyok
}
def teszteld_matrixokkal(matrixok):
for idx, matrix in enumerate(matrixok, start=1):
print(f"\n--- Teszt {idx} ---")
cel_x = len(matrix) - 1
cel_y = len(matrix[0]) - 1
talalatok = []
aktualis_ut = []
osszes_utvonal(matrix, 0, 0, cel_x, cel_y, aktualis_ut, talalatok)
eredmeny = utvonal_statisztika(talalatok)
if isinstance(eredmeny, dict):
print(f"Összes lehetséges útvonal száma: {eredmeny['ossz_utvonal_szam']}")
print(f"A legrövidebb út hossza: {eredmeny['legrovidebb_ut_hossza']} lépés.")
print(f"A legrövidebb út koordinátái: {eredmeny['legrovidebb_ut_koordinatak']}")
print(f"A lépések iránya: {', '.join(eredmeny['lepések_iranya'])}")
else:
print(eredmeny)
# Rendelkezésreálló adat
matrixok = [
[
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
],
[
[0, 0, 1, 0],
[0, 0, 1, 0],
[1, 0, 0, 0],
[0, 0, 0, 0]
],
[
[0, 0, 0],
[1, 1, 0],
[0, 0, 0]
]
]
teszteld_matrixokkal(matrixok)
--------------
176 ms
--- Teszt 1 ---
Összes lehetséges útvonal száma: 4
A legrövidebb út hossza: 6 lépés.
A legrövidebb út koordinátái: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
A lépések iránya: Lefelé, Lefelé, Lefelé, Jobbra, Jobbra, Jobbra
--- Teszt 2 ---
Összes lehetséges útvonal száma: 6
A legrövidebb út hossza: 6 lépés.
A legrövidebb út koordinátái: [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]
A lépések iránya: Lefelé, Jobbra, Lefelé, Lefelé, Jobbra, Jobbra
--- Teszt 3 ---
Összes lehetséges útvonal száma: 1
A legrövidebb út hossza: 4 lépés.
A legrövidebb út koordinátái: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
A lépések iránya: Jobbra, Jobbra, Lefelé, Lefelé
-------------
Futtatás; https://onecompiler.com/python#draft-tdxd
Nincsenek megjegyzések:
Megjegyzés küldése