StupidZombie.py

# Globals, hope there isn't something already in the global space with these names...
grid = list()
gridSize = 0
masterPermutationList = list(list())
coordinatePermutations = {(1,0), (0,1), (-1,0), (0,-1)}

# -100 (probably) indicates a bad x or y index
def getValueAt(x, y):
    if x >= gridSize or y >= gridSize:
        return -100

    if x < 0 or y < 0:
        return -100

    return grid[y * gridSize + x]

# We're just going to assume input is valid...
def parseGrid(size, gridAsString):
    global grid
    global gridSize
    grid.clear()
    gridSize = size
    if gridAsString[-1] == '\n':
        gridAsString = gridAsString[0:-1]
    stringGridArray = gridAsString.split(" ")
    for element in stringGridArray:
        grid.append(int(element))

# Walk around until we're at the end
def walk(alreadyTraveled, lastPair):
    global masterPermutationList
    currentX = lastPair[0]
    currentY = lastPair[1]

    # We're done!
    if currentX == gridSize - 1 and currentY == 0:
        masterPermutationList.append(alreadyTraveled)
        return    

    # We're not done! Figure out where we can go from here
    tempPairList = list()
    for element in coordinatePermutations:
        tempPair = (currentX + element[0], currentY + element[1])
        tempPairList.append(tempPair)

    # Make sure we're not walking off the edge or trying to go somewhere we've already been
    for element in tempPairList:
        if element[0] >= 0 and element[0] < gridSize and element[1] >= 0 and element[1] < gridSize and element not in alreadyTraveled:
            alreadyTraveledCopy = alreadyTraveled.copy()
            alreadyTraveledCopy.add(element)
            # Still here? Keep walking.
            walk(alreadyTraveledCopy, element)

# Run through the masterPermutationList and find the least-costliest path
def determineLeastCost():
    global masterPermutationList
    tempSet = set()
    originalIndex = (0, gridSize - 1)
    tempSet.add(originalIndex)
    walk(tempSet, originalIndex)

    bestPath = 0
    for path in masterPermutationList:
        pathTotal = 100
        for coordinate in path:
            pathTotal -= 5 * getValueAt(coordinate[0], coordinate[1])
        if pathTotal > bestPath:
            bestPath = pathTotal

    return bestPath

# Grab user input and run all the methods
def doEverything():
    print("Please enter size and then grid:")
    tempSize = int(input())

    if(tempSize <= 0): 
        return
    gridAsString = input()
    for i in range(0, tempSize - 1):
        gridAsString += " " + input() 

    parseGrid(tempSize, gridAsString)
    leastCost = determineLeastCost()
    print("Least cost is: " + str(leastCost))

doEverything()