小华地图寻宝（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 0total_num = 0xx = copy.deepcopy(x)yy = copy.deepcopy(y)while xx > 0:total_num += xx % 10 xx //= 10while yy > 0:total_num += yy % 10 yy //= 10 if total_num > k:return 0visited[x][y] = 1 result = 1if 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 resultprint(dfs(0, 0, m,n,k))
