Python Code


  • 0
    T

    class Solution(object):

    def findShortestWay(self, maze, ball, hole):
    
        """
    
        :type maze: List[List[int]]
    
        :type ball: List[int]
    
        :type hole: List[int]
    
        :rtype: str
    
        """
    
        def up(s):
    
            dist = 0
            c = s
    
            while c[0] >0 and maze[c[0]-1][c[1]] !=1:
                dist += 1
                c = (c[0]-1,c[1])
    
            return c, dist
    
        def down(s):
    
            dist = 0
            c = s
    
            while c[0] <len(maze)-1 and maze[c[0]+1][c[1]] !=1:
                dist += 1
                c = (c[0]+1,c[1])
    
            return c, dist
    
        def left(s):
    
            dist = 0
            c = s
    
            while c[1] >0 and maze[c[0]][c[1]-1] !=1:
                dist += 1
                c = (c[0],c[1]-1)
    
            return c, dist
    
        def right(s):
    
            dist = 0
            c = s
    
            while c[1] <len(maze[0])-1 and maze[c[0]][c[1]+1] !=1:
                dist += 1
                c = (c[0],c[1]+1)
    
            return c, dist
    
        def IsPassHole(cpos,npos):
    
            xmove,ymove = npos[0] - cpos[0], npos[1] - cpos[1]
    
            xsep, ysep = hole[0] - cpos[0], hole[1] - cpos[1]
    
            if xsep == 0:
                if ysep*ymove>-1 and abs(ymove) - abs(ysep) >-1:
                    return True, abs(ysep)
    
            if ysep == 0:
                if xsep*xmove>-1 and abs(xmove) - abs(xsep) >-1:
                    return True, abs(xsep)
    
            return False, 0
    
        def Direction(c,n):
            if n[0] > c[0]:
                return 'd'
            if n[1] > c[1]:
                return 'r'
            if c[0] > n[0]:
                return 'u'
            if c[1] > n[1]:
                return 'l'
    
        record = {(ball[0],ball[1]):{'dist':0,'pre':""}}
    
        stack = [{"pos":(ball[0],ball[1]),"dist":0,"pre":""}]
    
        traces = {}
    
        while len(stack)>0:
    
            current = stack.pop(0)
    
            #print current
            dist = current['dist']
            pos = current['pos']
            pre = current["pre"]
    
            n_up,d_up = up(pos)
            n_down,d_down = down(pos)
            n_left,d_left = left(pos)
            n_right,d_right = right(pos)
    
            #d_up, d_down, d_left, d_right = [one +dist for one in (d_up,d_down,d_left, d_right)]
    
            for n_pos,n_dist in [(n_down,d_down),(n_left,d_left),(n_right,d_right),(n_up,d_up)]:
    
                if n_dist<1:
                    continue
    
                judge ,sep = IsPassHole(pos, n_pos)
    
                n_dist += dist
    
                if judge:
                    rpos = pre+ Direction(pos, n_pos)
                    #print pos,n_pos, rpos
                    if sep+dist in traces:
                        traces[sep+dist] += [rpos]
                    else:
                        traces[sep+dist] = [rpos]
                    continue
    
                if (n_pos not in record):
    
                    di = Direction(pos, n_pos)
                    record[n_pos] = {'dist':n_dist, 'pre':pre+di}
                    stack += [{"pos": n_pos, "dist":n_dist,"pre":pre+di}]
                    continue
    
                if (n_dist < record[n_pos]["dist"]):
    
                    di = Direction(pos, n_pos)
                    npre = pre+di
                    record[n_pos] = {'dist':n_dist, 'pre':npre}
                    stack += [{"pos": n_pos, "dist":n_dist,"pre":npre}]
    
                if (n_dist == record[n_pos]["dist"]):
    
                    di = Direction(pos, n_pos)
                    npre = min(pre+di,record[n_pos]["pre"])
                    record[n_pos] = {'dist':n_dist, 'pre':npre}
                    stack += [{"pos": n_pos, "dist":n_dist,"pre":npre}]
    
        if len(traces)<1:
            return "impossible"
    
        #print record
        #print record[4,5]
    
        #print sorted(traces.items())
        return min(sorted(traces.items())[0][1])

Log in to reply
 

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