Python, Straightforward with Explanation

  • 4

    Let D be the taxicab distance, D(P, Q) = abs(Px - Qx) + abs(Py - Qy).

    Suppose the squirrel is already at the tree. The distance of his path will be:
    S = D(tree, nut_1) + D(nut_1, tree) + D(tree, nut_2) + D(nut_2, tree) + D(tree, nut_3) + ...
    and so
    S = sum_{i=1..N} 2 * D(tree, nut_i).

    At the beginning, the squirrel goes to some nut_k, then to the tree, then does the usual path described above except doesn't visit nut_k. Thus, his path has distance:
    D(squirrel, nut_k) + D(nut_k, tree) + S - (2 * D(tree, nut_k))
    which equals
    S + D(squirrel, nut_k) - D(nut_k, tree).

    def minDistance(self, height, width, tree, squirrel, nuts):
        def taxi(p, q):
            return abs(p[0] - q[0]) + abs(p[1] - q[1])
        S = sum(2 * taxi(tree, nut) for nut in nuts)
        return min(S + taxi(squirrel, nut) - taxi(nut, tree) for nut in nuts)

  • 0

    Very nicely explained.
    Trivial suggestion, but in last statement can't S be outside min? I mean to say
    return S + min(taxi(squirrel, nut) - taxi(nut, tree) for nut in nuts)

  • 0

    @siberiancrane Yes, it could.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.