找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: huangyingw
收起左侧

[面经题目讨论] Monkey Grid 问题边界值的问题

[复制链接]

1

主题

1

精华

70

积分

资深会员

Rank: 2

积分
70
发表于 9-4-2015 11:50 PM | 显示全部楼层
题目表述得不清楚啊。另外,觉得bfs+backtracking就好。

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-5-2015 08:26 AM | 显示全部楼层
也说下我的想法,考虑从原点开始往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足够了。

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-5-2015 08:49 AM | 显示全部楼层
  1. from queue import Queue& p$ ~/ u( z, k, l8 d

  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]]; m5 U/ ?/ u0 i/ Z$ w
  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()7 ~" o) @& j$ }8 O' {: }
  8.         queue = Queue()9 l# g1 o- h$ F) M4 u# A, e
  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):* b- G: A! ?/ D! A
  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))1 ^* B5 j+ m1 v7 |6 ^) ~
  18.                                 visited.add((nx, ny)): |8 c, A& \" n# R, x
  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. 7 j; u! q% R! ]+ m1 D* g/ F
  23. # p! v7 D5 t1 z& d
  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
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表