找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

123
返回列表 发新帖
楼主: huangyingw
收起左侧

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

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-5-2015 08:58 AM | 显示全部楼层
实际上由于四个象限是对称的,我们可以以只求出第1象限内的可行点数,仅让其往X轴正向或Y轴正向走, K2 I" l& T0 g9 S6 Y
  1. from queue import Queue
    0 E; W" P7 ]) f1 w( u

  2. ' \5 z% k; M7 h" ^1 \! J) n( ]
  3. def solveMonkeyGrid(digitsSumLimit):
    8 o: O9 {, h0 t1 P9 N* j
  4.         steps = [[1, 0], [0, 1]]
    8 R' p7 g4 \8 w" Y! k9 v
  5.         sumDigits = lambda n: sum([int(c) for c in str(abs(n))])0 j% Z3 x. T- h

  6. - b9 [/ g# E4 u0 R$ l
  7.         visited = set()
    - ~3 c) w! d5 @, X! V
  8.         queue = Queue(); W* B0 g" e! c& K
  9.         queue.put((0, 0))' A$ t2 a/ R  |' V4 T9 |0 e  ?
  10.         visited.add((0, 0))
    5 t# L( W+ C6 R0 L+ [; U
  11.         cnt = 1
    * h8 U! J5 b' W
  12.         while not queue.empty():
    7 ^7 w3 X3 [' Z, b
  13.                 x, y = queue.get()& a' l& N& v5 X" b/ `0 z
  14.                 for i in range(2):
    " d3 @, D- w" Y: F# X
  15.                         nx, ny = x + steps【i】[0], y + steps【i】[1]
    ! h- b; {9 B8 k0 `
  16.                         if (nx, ny) not in visited and sumDigits(nx) + sumDigits(ny) <= digitsSumLimit:8 q7 e7 t  c* e5 ^7 ?1 Q& g0 `
  17.                                 queue.put((nx, ny))6 D) L" Y; u" C& O) N& N
  18.                                 visited.add((nx, ny))6 _/ C7 @' a7 y/ t
  19.                                 cnt += 1
    1 w* k  c9 t' n5 E
  20.        
    ( u6 H+ G$ u8 l' j, e5 K  k/ ]0 F
  21.         return cnt
    0 A! c, I! Y/ Q5 j* N* L

  22. 9 N% D1 y* X& @
  23. 5 e4 Y4 }. x9 Y* o  _
  24. # test( S- B: Y# r( G1 k# X. D
  25. print(solveMonkeyGrid(19))
    0 L4 j' x  j% W6 O! c7 @
复制代码
: L& L/ f# ]5 U* {$ Y, c# Y
得到结果是25920,这一结果包含了原点以及X轴和Y轴上的可行点,由分析我们知道在X正半轴、Y正半轴上的可行点数是298,这样总的可行点数就是(25920-298*2-1)*4 + 298*4 + 1 = 102485
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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