doolhof =  [
    ['.', '.', '.', '.', '.'],
    ['.', '*', '.', '.', '.'],
    ['.', '.', 'S', '*', 'F'],
    ['.', '*', '.', '.', '.'],
    ['.', '*', '*', '.', '.']
]



#Geeft het korste pad weer
def korstePad(doolhof, startX, startY, finishX, finishY):
    index = 1
    aantalStappen = 0
    loopController = True

    maxAaantalStappen = berekenMaxAantalStappen(doolhof)

    PositionCheck(doolhof, startX, startY, index)


    #Vult grid met cijfers om het kortste pad te vinden
    while(loopController):

        for rij in range(len(doolhof)):
            for kolom in range(len(doolhof[0])):
                if (doolhof[rij][kolom] == index):
                    PositionCheck(doolhof, rij, kolom, index + 1)

        index += 1

        #Als de waarde op de finish is verandert, dan betekent is dit in de laatste iteratie gebeurd. Hierdoor kunnen we aannemen dat de index het # stappen is
        if (doolhof[finishX][finishY] != "F"):
            loopController = False

        if (index > maxAaantalStappen ):
            loopController = False
            print("Pad bestaat niet")
            #RETURNEN NAAR MENU ANDERS GAAT DE FUNCTIE GEWOON VERDER NAAR HET VISUALEREN


    aantalStappen = index #Aantal stappen
    print(aantalStappen, "Stappen voor van S naar F") #Weghalen

    visualiseerKorstepad(doolhof, startX, startY, finishX, finishY, index - 1)

#Berekent het maximaal aantal stappen
def berekenMaxAantalStappen(doolhof):
    lengte = len(doolhof)
    breedte = len(doolhof[0])

    return lengte*breedte

def visualiseerKorstepad(doolhof, startX, startY, finishX, finishY, n):
    doolhof[finishX][finishY] = "F"
    loopController = True

    visualiseerPad(doolhof, finishX, finishY, n)

    while (loopController):

        for rij in range(len(doolhof)):
            for kolom in range(len(doolhof[0])):
                if (doolhof[rij][kolom] == "O"):
                    visualiseerPad(doolhof, rij, kolom, n)
                    #break?

        n -= 1
        if (n == 0):
            loopController = False

    verwijderGetallenInDoolhof(doolhof)
    toonDoolhof(doolhof)


def visualiseerPad(doolhof, x, y, n):
    if ((NotoutOfBoundsCheck(x - 1, y) and (doolhof[x - 1][y] == n))):
        # Function that checks endposition
        doolhof[x - 1][y] = "O"

    elif ((NotoutOfBoundsCheck(x + 1, y)) and (doolhof[x + 1][y] == n)):
        # Function that checks endposition
        doolhof[x + 1][y] = "O"

    elif ((NotoutOfBoundsCheck(x, y - 1)) and (doolhof[x][y - 1] == n )):
        # Function that checks endposition
        doolhof[x][y - 1] = "O"

    elif ((NotoutOfBoundsCheck(x, y + 1)) and (doolhof[x][y + 1] == n )):
        # Function that checks endposition
        doolhof[x][y + 1] = "O"


#Checkt startPositie
def PositionCheck(doolhof, x, y, n):

    if ((NotoutOfBoundsCheck(x - 1, y)) and ((doolhof[x - 1][y] == ".") or (doolhof[x - 1][y] == "F"))):
        #Function that checks endposition
        doolhof[x - 1][y] = n

    if ((NotoutOfBoundsCheck(x + 1, y)) and ((doolhof[x + 1][y] == ".") or (doolhof[x + 1][y] == "F"))):
        # Function that checks endposition
        doolhof[x + 1][y] = n

    if ((NotoutOfBoundsCheck(x, y-1)) and ((doolhof[x][y - 1] == ".") or (doolhof[x][y - 1] == "F"))):
        # Function that checks endposition
        doolhof[x][y - 1] = n

    if ((NotoutOfBoundsCheck(x, y + 1)) and ((doolhof[x][y + 1] == ".") or doolhof[x][y + 1] == "F")):
        # Function that checks endposition
        doolhof[x][y + 1] = n

#Controleert out of bounds errors
def NotoutOfBoundsCheck(x, y):

     # Controleert de lengte van het doolhof
    if ((x < 0) or (x >= len(doolhof))):
        return False

    # Controleert de breedte van het doolhof
    elif ((y < 0) or (y >= len(doolhof[0]))):
        return False

    else:
        return True

def toonDoolhof(doolhof):
    for i in range(len(doolhof[0]) + 2):
        print("-", end=" ")
    print('\n')

    for i in range(len(doolhof)):
        if i != 0:
            print('\n')
        print('|', end=" ")
        for j in range(len(doolhof[i])):
            print(doolhof[i][j], end=" ")
        print('|', end=" ")

    print('\n')
    for i in range(len(doolhof[0]) + 2):
        print("-", end=" ")

    print('\n')

def verwijderGetallenInDoolhof(doolhof):

    for rij in range(len(doolhof)):
        for kolom in range(len(doolhof[0])):
            if (coordinaatIsInteger(rij, kolom, doolhof)):
                doolhof[rij][kolom] = "."

def coordinaatIsInteger(rij, kolom, doolhof):

    if (doolhof[rij][kolom] == "*"):
        return False

    elif (doolhof[rij][kolom] == "S"):
        return False

    elif (doolhof[rij][kolom] == "F"):
        return False

    elif (doolhof[rij][kolom] == "O"):
        return False

    else:
        return True

korstePad(doolhof, 2, 2, 2, 4)