ПОИСК общего количества путей с использованием функции поиска с возвратом

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], то есть самой правой нижней ячейки.

bool isValid(int x, int y)
{
    if (x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}
void countPaths(int x, int y)
{
    // cout << x << y << endl;
    if (x == n - 1 && y == n - 1)
    {
        paths++;
        return;
    }

    if (isValid(x, y))
    {
        visited[x][y] = true;
        countPaths(x, y + 1);
        countPaths(x + 1, y);
    }

    return;
}

Сохранение путей и посещений как глобальных переменных, I реализовал вышеупомянутый подход.

For n=2 (1+1): 2
For n=3 (2+1): 6
For n=4 (3+1): 20
For n=5 (4+1): 70

однако этот подход не будет жизнеспособным для n = 20. Я бы посоветовал попробовать Dynami c Programming, так как это упростит процесс!