.......E <-end
........
........
........
........
........
........
S....... <-start
不幸的是,您不能使用“任何标准路径查找算法”,因为您的路径可能不是最短路径。您必须专门使用考虑所有路径的朴素搜索(例如深度优先或广度优先搜索)。
然而,由于您不关心如何到达一个图块,您可以使用一种称为“动态规划”的技术。对于每个位置(i,j),到达该位置的方式数(称为waysi,j(n))为:
waysi,j(n)= waysi-1,j(n-1)+ waysi+1,j(n-1)+ waysi,j-1(n-1)+ waysi,j+1(n-1)+ waysi+1,j+1(n-1)+ waysi-1,j+1(n-1)+ waysi+1,j-1(n-1)+ waysi-1,j-1(n-1)
也就是说,国王可以在1步内从任何相邻的格子移动:
waysi,j(n) = sumneighbors(i,j)(waysneighbor(n-1))
因此,例如在Python中:
SIZE = 8
cache = {}
def ways(pos, n):
r,c = pos
if not (0<=r<SIZE and 0<=c<SIZE):
return 0
elif n==0:
return 1 if (r,c)==(0,0) else 0
else:
args = (pos,n)
if not args in cache:
cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1)
return cache[args]
演示:
>>> ways((7,7), 15)
1074445298
上述技术被称为记忆化,相比动态规划更容易编写,因为您不需要真正考虑执行操作的顺序。随着我们执行一系列越来越大的查询,您可以看到缓存增长:
>>> cache
{}
>>> ways((1,0), 1)
1
>>> cache
{((1, 0), 1): 1}
>>> ways((1,1), 2)
2
>>> cache
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0}
>>> ways((2,1), 3)
5
>>> cache
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5}
在Python中,还可以使用@cached
或@memoized
装饰器来避免编写整个代码块在最后的else:
语句中。其他编程语言也有其他自动执行记忆化的方法。
以上是一种自顶向下的方法。它有时会产生非常大的堆栈(您的堆栈将随着n
的增长而增长)。如果您想要超级高效地避免不必要的工作,可以采用自底向上的方法,模拟国王可能出现的所有位置,1步、2步、3步等:
SIZE = 8
def ways(n):
grid = [[0 for row in range(8)] for col in range(8)]
grid[0][0] = 1
def inGrid(r,c):
return all(0<=coord<SIZE for coord in (r,c))
def adjacentSum(pos, grid):
r,c = pos
total = 0
for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]:
delta_r,delta_c = neighbor
(r2,c2) = (r+delta_r,c+delta_c)
if inGrid(r2,c2):
total += grid[r2][c2]
return total
for _ in range(n):
grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)]
from pprint import pprint
pprint(grid)
return grid
演示:
>>> ways(0)
[[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
>>> ways(1)
[[0, 1, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
>>> ways(2)
[[3, 2, 2, 0, 0, 0, 0, 0],
[2, 2, 2, 0, 0, 0, 0, 0],
[2, 2, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
>>> ways(3)
[[6, 11, 6, 4, 0, 0, 0, 0],
[11, 16, 9, 5, 0, 0, 0, 0],
[6, 9, 6, 3, 0, 0, 0, 0],
[4, 5, 3, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
>>> ways(4)
[[38, 48, 45, 20, 9, 0, 0, 0],
[48, 64, 60, 28, 12, 0, 0, 0],
[45, 60, 51, 24, 9, 0, 0, 0],
[20, 28, 24, 12, 4, 0, 0, 0],
[9, 12, 9, 4, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]