Find the path think as coordinate plane-CodePudding

def path(given_map, x, y):
    x = given_map[0][0] 
    y = given_map[0][0]
    cnt = 0

    if x == len(given_map) and y == len(given_map):
        cnt  = 1
        return cnt

    else:
        if x < len(given_map) and y < len(given_map):
            return path(given_map, x, y)
    
        elif x < len(given_map) and y == len(given_map):
            return path(given_map, x, y)
    
        elif x == len(given_map) and y < len(given_map):
            return path(given_map, x, y)
        else:
            cnt = 0
            return cnt
    
if __name__ == '__main__':
    input_map = [[1,2,9,4,9],
                 [1,5,8,7,9], 
                 [9,3,9,9,2], 
                 [2,3,7,5,9], 
                 [1,9,9,1,0]]
    print(path(input_map, 0, 0))

    input_map = [[1,1,2], 
                 [1,2,2], 
                 [1,2,0]]
    print(path(input_map, 0, 0))

The n*n list must be input to create a function that returns the number of paths that can reach from the starting point [0][0] to the ending point [n-1][n-1].

Movement can only be done downward and right, and can only be moved in one direction by the number shown in the corresponding x and y coordinates.

It does not include cases outside the map after movement.

The above code is implemented as much as possible within my ability. How can I modify it to function normally?

CodePudding user response：

Unless you are required to implement this using recursion, I would suggest a BFS (Breadth First Search) approach using a dictionary to track the positions/count that you have reached at each step of the progression:

def path(M):
    result = 0              # final result
    bounds = range(len(M))  # inside map
    paths  = {(0,0):1}      # one path at start
    while paths:            # spread counts
        nextPos = dict()    # track next positions
        for (x,y),count in paths.items():          # extend positon/count
            if x == y == len(M)-1: result  = count # capture final count
            dist = M[x][y]                         # travel distance
            if not dist: continue                  # no movement ...
            for x2,y2 in [(x,y dist),(x dist,y)]:  # travel down & right
                if x2 in bounds and y2 in bounds:  # propagate count
                    nextPos[x2,y2] = nextPos.get((x2,y2),0) count
        paths = nextPos # next step on paths
    return result
            
input_map = [[1,2,9,4,9],
             [1,5,8,7,9], 
             [9,3,9,9,2], 
             [2,3,7,5,9], 
             [1,9,9,1,0]]
print(path(input_map))  # 2

input_map = [[1,1,2], 
             [1,2,2], 
             [1,2,0]]
print(path(input_map))  # 1

If you are required to implement a recursive approach, the function can be adapted like this (returning the sum of recursive path counts) but then it won't be a BFS anymore:

def path(M,x=0,y=0):
    if x == y == len(M)-1: return 1  # goal reached
    dist = M[x][y]                   # travel distance
    if not dist: return 0            # no movement
    bounds = range(len(M))           # inside map
    return sum(path(M,x2,y2) for x2,y2 in [(x,y dist),(x dist,y)]
               if x2 in bounds and y2 in bounds) # sum of paths