[使用回溯找到路径总数

Question

我正在尝试使用回溯来计算20x20网格（ProjectEuler＃15）中的总路径。任何帮助将不胜感激（我知道可以使用递归或备忘录来解决，但我想使用回溯来解决）

def isvalid(maze,n,x,y):
    if x<0 or y<0 or x>n or y>n :
        return False
    else: return True

def countPaths(maze,x,y,n,used,count):
    if x==n-1 or y==n-1:
        count+=1
        return
    if isvalid(maze,n,x,y):
        used[x][y]=True
        if (x+1<n and used[x+1][y]==False):
            countPaths(maze,x+1,y,n,used,count)
        if (x-1>0 and used[x-1][y]==False):
            countPaths(maze,x-1,y,n,used,count)
        if (y+1<n and used[x][y+1]==False):
            countPaths(maze,x,y+1,n,used,count)
        if (y-1>0 and used[x][y-1]==False):
            countPaths(maze,x,y-1,n,used,count)
        used[x][y]=False
    return

Answer 1

由于在基本情况下，每当行或列的末尾出现时，您仅返回1，这将产生错误的答案。您应该增加一个计数器，以表示能够到达最后[n-1] [n-1]，即最右边的底部单元格的次数。

if(x==n-1 and y==n-1)
count++;

我建议尝试动态编程，因为这样可以简化过程！