Monkey Grid 问题边界值的问题

题目是这样子的:

Thereis a monkey which can walk around on a planar grid. The monkey canmove one space at a time left, right, up or down. That is, from (x,y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).Points where the sum of

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Unicode MS">当K=25时,单个下标的最大值是898,这个值是怎么算出来的,如何证明?

1. from collections import deque
   
2. def can_access(x,y,k):
   
3.   if x<0:
   
4.     x=-x
   
5.   if y<0:
   
6.     y = -y
   
7.   return sum([ord(i)-ord('0') for i in str(x)]) + sum([ord(i)-ord('0') for i in str(y)]) <= k
   
8. 
   
9. def monkey_walk(k):
   
10.   best = 0
    
11.   dx=[0,0,-1,1]
    
12.   dy=[1,-1,0,0]
    
13.   Q = deque()
    
14.   Q.append((0,0))
    
15.   visited = set()
    
16.   visited.add((0,0))
    
17.   while Q:
    
18.     head = Q.popleft()
    
19.     for d in xrange(0,4):
    
20.       x,y = head[0]+dx[d], head[1]+dy[d]
    
21.       if (x,y) in visited or not can_access(x,y,k):
    
22.         continue
    
23.       Q.append((x,y))
    
24.       visited.add((x,y))
    
25.       best = max(best,x)
    
26.       best = max(best,y)
    
27.   print 'best', best
    
28.   return len(visited)
    
29. 
    
30. print monkey_walk(25)
    
31.                   

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

bfs搜索出来 的

Linzertorte 发表于 2015-9-4 05:23
bfs搜索出来 的

能不能数学证明呢?

hoho best best

Linzertorte 发表于 2015-9-4 05:42

嘿嘿,代码我也有,不过是java实现的,帮我留意一下有没有google全球招聘的职位吧?

用归纳法试试？

就说k=24到k=25
k=24, 可以到达(0,798), k=25可以到达(0,898)
798+1 ,数位加1,是799,然后再1的话,就是800,直到加到899，都是数位和<=25.
这个就证明了一个方向了。。

哦证明了。。 直到加到898， 因为 899就超了，所以f(25)<899.