Рассчитать количество путей в сетке сверху вниз слева направо

Question

Мне нужно рассчитать количество путей сверху вниз слева направо, где действительный путь - это путь, который пересекает все квадраты в сетке (и ровно один раз для каждого квадрата)

Я использую техника возврата. К сожалению, count равно 0 в конце расчета. При печати t я вижу, что она никогда не достигает n-1.

Что не так с моим алгоритмом?

n = 4
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):

    print(t)

    global count

    # check if we reached target
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            # not on time, prune the tree here
            return 
        elif t == n * n:
            # completed a full path in the grid and on time
            count += 1 

    if t > n * n:
        return

    # Right
    if x + 1 < n and m[x + 1][y] == False:
        m[x + 1][y] = True
        num_of_paths(m, x + 1, y, t + 1)
        m[x + 1][y] = False

    # Left
    if x - 1 > 0 and m[x - 1][y] == False:
        m[x - 1][y] = True
        num_of_paths(m, x - 1, y, t + 1)
        m[x - 1][y] = False

    # Down
    if y + 1 < n and m[x][y + 1] == False:
        m[x][y + 1] = True
        num_of_paths(m, x, y + 1, t + 1)
        m[x][y + 1] = False

    # Up
    if y - 1 > 0 and m[x][y - 1] == False:
        m[x][y - 1] = True
        num_of_paths(m, x, y - 1, t + 1)
        m[x][y - 1] = False


num_of_paths(m, 0, 0, 0)
print(count)

Answer 1

Существуют следующие проблемы:

• Начальная ячейка не помечена m[0][0] = True, поэтому после перехода вправо алгоритм go снова выйдет и фактически дважды посетит эту ячейку. Чтобы решить эту проблему, вы можете переместить код для управления значениями m из того места, где он у вас есть (4 раза), и применить его к текущей ячейке (один раз). Это включает проверку if m[..][..] и присвоения True и False.
• Условия if, которые относятся к левому и верхнему направлениям, должны сравнивать координату с >= 0, а не с > 0: нулевое значение для координаты все еще находится в пределах диапазона.
• t должно начинаться с 1, поскольку вы сравниваете его значение с n * n. Или же вы должны сравнить с n * n - 1. В моем исправлении ниже я начну с t = 1.
• Не является реальной проблемой, но после выполнения count += 1 имеет смысл немедленно return, поскольку больше нет возможности расширять путь дальше. .

Некоторые другие замечания:

• Когда n четный, допустимый путь отсутствует, поэтому даже после исправления функция связана с в этом случае верните 0
• Число путей, которые этот алгоритм посещает, является экспоненциальным, O (2 ^n² ) . Для n> 6 , не ждите этого ...

Вот исправленная версия вашего кода. Комментарии должны уточнить, что было изменено и почему:

n = 5
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):
    global count
    # Moved the "visited" check to here. No need to add `== True`.
    if m[x][y]: 
        return
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            return 
        else: # Removed the unnecessary condition here
            count += 1 
            # Added a return here
            return
    # Removed an if-block of which the condition could never be true
    # Moved the "visited" marking to here:
    m[x][y] = True
    if x + 1 < n:
        num_of_paths(m, x + 1, y, t + 1)
    # Corrected "> 0" to ">= 0"
    if x - 1 >= 0:
        num_of_paths(m, x - 1, y, t + 1)
    if y + 1 < n:
        num_of_paths(m, x, y + 1, t + 1)
    # Corrected "> 0" to ">= 0"
    if y - 1 >= 0:
        num_of_paths(m, x, y - 1, t + 1)
    # Moved the "visited" unmarking to here:
    m[x][y] = False

# Corrected the last argument
num_of_paths(m, 0, 0, 1)
print(count)

Answer 2

этот код работает

n = 3
count=0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m,x,y):


    # setting (x,y) position in m = True as we have crossed this square now


    m[y][x]=True
    global count
    # check if we reached target

    if x == (n - 1) and y == (n - 1):

        # check if we haven't missed any square

        for i in m:   
            if False in i:
                m[y][x]=False
                return 

        # increment count if we visited all squares

        count+=1    
        m[y][x]=False
        return 


     # setting up legel directions in which current point(x,y) should head next
    dir={'up','down','left','right'}
    if x==0:
        dir-={'left'}
    if x==n-1:
        dir-={'right'}
    if y==0:
        dir-={'up'}
    if y==n-1:
        dir-={'down'}
    # now we have all legal directions that (x,y) could go to

    # now iterate over all possible directions of (x,y)
    for i in dir:
        if i=='left':      # left means (x,y) will change to (x-1,y) i.e. change is (-1,0)
            if m[y][x-1]==False:   # it means left of (x,y) havent yet crossed i.e. it is legel to visit now
                num_of_paths(m,x-1,y)
    # similiarly for other possible directions

        if i=='right':
            if m[y][x+1]==False:
                num_of_paths(m,x+1,y)

        if i=='up':
            if m[y-1][x]==False:
                num_of_paths(m,x,y-1)

        if i=='down':
            if m[y+1][x]==False:
                num_of_paths(m,x,y+1)


num_of_paths(m,0,0)
print(count)

сообщите мне, если есть какая-то проблема