Monkey Grid 问题边界值的问题

cszeus

题目表述得不清楚啊。另外，觉得bfs+backtracking就好。

uuuouou

也说下我的想法，考虑从原点开始往X轴正方向走，这样Y坐标为0，提供的digits sum一直是0，由于1位数、2位数的digit sum肯定不到19（最大也就99 => 18），这样3位数可以走过199、200，继续往前走过289、290，但走到298就不能再沿着X轴正方向继续走了。
( a! ?3 \4 q2 o, l' K同样地，沿着其他3个轴向也最多只能走到绝对值为298的位置，这样，以x=+-298，y=+-298构成的正方形就是最外的边界了，这个区域范围内的整数点少于600 * 600个，所以BFS足够了。

uuuouou

1. from queue import Queue
   
2. 
   . f+ ?' v  r6 N- [4 Y& ]
3. def solveMonkeyGrid(digitsSumLimit):
   ' J2 y, p& f2 }
4.         steps = [[-1, 0], [1, 0], [0, -1], [0, 1]]
   
5.         sumDigits = lambda n: sum([int(c) for c in str(abs(n))])
   ; q0 q0 L) u' H. V8 c5 k
6. 
   5 D- }) Y  ~$ o0 ?  S  H0 a
7.         visited = set()
   
8.         queue = Queue()
   
9.         queue.put((0, 0))
   1 C4 Q# _! h% i6 M8 F( [
10.         visited.add((0, 0))
    , w6 t7 E3 p9 _) `- W: y" }7 r7 Z
11.         cnt = 1
    ' B, |/ }$ y) {% }) c: D3 H) z
12.         while not queue.empty():
    ( Q7 r" T9 \+ T7 `" V* k
13.                 x, y = queue.get()
    1 Y5 i) A1 G+ s. `9 T) b  Q
14.                 for i in range(4):
    
15.                         nx, ny = x + steps【i】[0], y + steps【i】[1]
    ' n0 ~/ C5 x3 H& c5 C# `7 _
16.                         if (nx, ny) not in visited and sumDigits(nx) + sumDigits(ny) <= digitsSumLimit:
    , G9 w$ u; w8 E
17.                                 queue.put((nx, ny))
    
18.                                 visited.add((nx, ny))
    
19.                                 cnt += 1
    3 q9 Z. K* Z# i2 a/ H5 A
20.        
    7 [- P6 l0 X% Q9 H: J
21.         return cnt
    : @" i& u$ \6 |) N
22. 
    
23. 
    
24. # test
    + j/ J% E& z8 Y8 \
25. print(solveMonkeyGrid(19))
    * {+ y) H0 P$ G, Q" z

复制代码

% f; U' @8 o1 t' y: [+ a, }* i: C5 ]结果是102485