从左上角到右下角计算网格中的路径数

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，因此向右移动后，算法将再次向左移动，并实际访问该单元格两次。要解决此问题，您可以将用于管理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)

如果有问题，请告诉我