推荐订阅源

踩方格：有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a.每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步(n<=20)，共有多少种不同的方案。
2种走法只要有一步不一样，即被认为是不同的方案。
思路：递归
因为假设是无穷大的平面，最多走20步，也就是起点是平面中的任意一个点
初始化visited[30][50]长度的二维列表，假设从visited[25][25]，
往3个方向走20步都不会越界，可以满足题目要求
从 (i,j) 出发，走n步的方案数，等于以下三项之和：
向北走，从(i-1,j)出发，走n-1步的方案数。前提： (i+1,j)还没走过
向东走，从(i,j+1)出发，走n-1步的方案数。前提： (i,j+1)还没走过
向西走，从(i,j-1)出发，走n-1步的方案数。前提： (i,j-1)还没走过
python代码实现：

 1 # 记录该方格是否走过，0-未走过；1-走过
 2 visited = []
 3 
 4 def Ways(i, j, n):
 5     global visited
 6     if n == 0:
 7         return 1
 8     visited[i][j] = 1
 9     num = 0
10     # 向北走
11     if visited[i-1][j] == 0:
12         num += Ways(i-1, j, n-1)
13     # 向东走
14     if visited[i][j+1] == 0:
15         num += Ways(i, j+1, n-1)
16     # 向西走
17     if visited[i][j-1] == 0:
18         num += Ways(i, j-1, n-1)
19     visited[i][j] = 0
20     return num
21 
22 
23 def main():
24     # n-步数
25     n = int(input())
26     global visited
27     # 30行，50列
28     visited = [[0] * 50 for i in range(30)]
29 
30     steps = Ways(25, 25, n)
31     print("走%d步，共有%d种不同的方案" % (n, steps))
32 
33 
34 if __name__ == '__main__':
35     main()