unser Prof hat ne Aufgabe gegeben wo wir rekursiv den kürzesten Weg aus einem Labyrinth finden sollten.
So weit so gut, das Attest habe ich schon also bestanden der Labyrinth ist nicht schwer gewesen, wo ich jetzt aber zu Hause mit anderen Labyrinthen probiere funktioniert es ab und zu und ab und zu nicht. Das Problem kann ich nicht genau identifizieren, schein aber so wenn um das Ziel nur einen Weg gibt versagt es.
Code: Alles auswählen
__author__ = 'Jakob'
import random
import copy
import sys
import os
import time
delimiter = "x"
finish = "E"
def feld_erstellen(feld, file):
datei = open(file, "r")
x = 0
y = 0
for line in datei:
feld.append([])
for char in line.rstrip():
feld[x].append(char)
y += 1
y = 0
x += 1
def feld_ausgeben(feld, route):
x = 0
y = 0
temp = ""
i = 0
while i < route.__len__():
while x < feld.__len__():
while y < feld[x].__len__():
if(route[i][0] == x and route[i][1] == y):
temp += "O"
else:
temp += feld[x][y]
y += 1
print(temp)
temp = ""
y = 0
x += 1
x = 0
time.sleep(0.5)
os.system("cls")
i += 1
def check(zeichen):
if(zeichen == finish):
return True
elif(zeichen == delimiter):
return False
def schon_gegangen(x,y, route):
i = 0
while i < route.__len__():
if(route[i][0] == x and route[i][1] == y):
return True
i += 1
return False
def backtrack(x,y, feld, route):
if(schon_gegangen(x, y, route)):
return False
else:
route.append((x, y))
if(check(feld[x][y]) == True):
return route
elif(check(feld[x][y]) == False):
return False
i = 0
returnvalue = 0
temp_route = []
while i < 4: # im Uhrzeigersinn
if(i == 0):
returnvalue = backtrack(x-1, y, feld, copy.copy(route))
elif(i == 1):
returnvalue = backtrack(x, y+1, feld, copy.copy(route))
elif(i == 2):
returnvalue = backtrack(x+1, y, feld, copy.copy(route))
elif(i == 3):
returnvalue = backtrack(x, y-1, feld, copy.copy(route))
i += 1
if(returnvalue != False):
if(temp_route.__len__() == 0):
temp_route = returnvalue
if(returnvalue.__len__() < temp_route.__len__()):
temp_route = returnvalue
if(temp_route.__len__ == 0):
return False
else:
return temp_route
x = 1
y = 1
route = []
feld = []
file = input("Geben Sie die Datei ein: ")
feld_erstellen(feld, file)
lol = backtrack(1, 1, feld, route)
feld_ausgeben(feld, lol)
Code: Alles auswählen
xxxxxxx
x x x
x xx x
x x
xxxx x
x x
x xx xx
x E x
xxxxxxxCode: Alles auswählen
xxxxxxx
x x x
x xx x
x x
xxxx x
x x
x xx xx
x E x
xxxxxxx
