OD C卷 - 小华地图寻宝

小华地图寻宝（200）

• m x n的矩阵中，横纵坐标范围【0，n-1】【0，m-1】
• 横纵坐标数位之和<=k的方格中存在1g黄金，如（21,13）坐标中2+1+1+3 <= 10；
• 从（0,0）入口，只能上 下 左 右四个方向行走一格，最多能获取多少g黄金？

输入描述：
输入m n k ，m n的范围在【0,50】，k的范围在【0,100】

输出描述:
最多获取多少黄金？

示例1
输入：
40 40 18
输出：
1484

示例2
输入：
5 4 7
输出：
20

思路：

• DFS
• 函数递归实现

 sys.setrecursionlimit(20000) m, n, k = list(map(int, input().strip().split())) visited = [[0 for j in range(n)] for i in range(m)]  def dfs(x, y, m, n, k) :     if x < 0 or y < 0 or x >= m or y >= n or visited[x][y]==1:         return 0     total_num = 0     xx = copy.deepcopy(x)     yy = copy.deepcopy(y)     while xx > 0:         total_num += xx % 10          xx //= 10     while yy > 0:         total_num += yy % 10          yy //= 10       if total_num > k:         return 0            visited[x][y] = 1      result = 1     if x+1 <= m:         result += dfs(x + 1, y, m,n,k)          if x-1 >= 0:         result += dfs(x - 1, y, m,n,k)          if y+1 <= n:         result += dfs(x,y+1, m,n,k)          if y-1 >=0 :         result += dfs(x, y-1, m,n,k)     return result   print(dfs(0, 0, m,n,k))