my python solution, inspired by A* algorithm


  • 4
    W

    The expected min distance between p1 and p2 is d = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]).
    From p1 (or the following positions), we may have two choices, move a step towards p2 or a step far away from p2 (if we do this, the min distance we can expect is d + 2, so we needn't think about them until all the expected min distance way are blocked).
    And I use stack to find the possible way greedily.
    Here is my code:

    class Solution(object):
        def cutOffTree(self, forest):
            """
            :type forest: List[List[int]]
            :rtype: int
            """
            nrow, ncol = len(forest), len(forest[0])
            forest.append([0] * ncol)
            for row in forest:
                row.append(0)
    
            trees = {(i, j) for i in range(nrow) for j in range(ncol)
                     if forest[i][j] > 1}
    
            canReach = {(0, 0)}
            stack = [(0, 0)]
            while stack:
                i, j = stack.pop()
                for i2, j2 in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                    if forest[i2][j2] != 0 and (i2, j2) not in canReach:
                        canReach.add((i2, j2))
                        stack.append((i2, j2))
    
            if trees.difference(canReach):
                return -1
    
            def get_sp(p1, p2):
                theMin = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
                stack1, stack2 = [p1], []
                used, visited = {p1}, {p1}
    
                while 1:
                    if not stack1:
                        stack1, stack2 = stack2, stack1
                        used.update(stack1)
                        theMin += 2
    
                    p = stack1.pop()
                    if p == p2:
                        break
    
                    i, j = p
                    add1, add2 = [], []
    
                    if i == p2[0]:
                        add2.append((i - 1, j))
                        add2.append((i + 1, j))
                    elif i < p2[0]:
                        add2.append((i - 1, j))
                        add1.append((i + 1, j))
                    else:
                        add1.append((i - 1, j))
                        add2.append((i + 1, j))
    
                    if j == p2[1]:
                        add2.append((i, j - 1))
                        add2.append((i, j + 1))
                    elif j < p2[1]:
                        add2.append((i, j - 1))
                        add1.append((i, j + 1))
                    else:
                        add1.append((i, j - 1))
                        add2.append((i, j + 1))
    
                    for v in add1:
                        if forest[v[0]][v[1]] != 0 and v not in used:
                            visited.add(v)
                            used.add(v)
                            stack1.append(v)
                    for v in add2:
                        if forest[v[0]][v[1]] != 0 and v not in visited:
                            visited.add(v)
                            stack2.append(v)
    
                return theMin
    
            seq = sorted(trees, key=lambda x: forest[x[0]][x[1]])
            if seq[0] != (0, 0):
                seq.insert(0, (0, 0))
            return sum(get_sp(seq[i], seq[i + 1]) for i in range(len(seq) - 1))
    

  • 0
    M

    @wufangjie Great solution! You are the only one that truly passed this problem using Python so far!


  • 1
    M

    A nice explanation of A* algorithm (pseudo code): http://web.mit.edu/eranki/www/tutorials/search/

    The general idea is :

    g is the cost it took to get to the node, most likely the number of squares we passed by from the start. h is our guess as to how much it'll cost to reach the goal from that node. f is the cost function, and f = g+h.

    struct node {
        node *parent;
        int x, y;
        float f, g, h;
    }
    
    // A*
    initialize the open list
    initialize the closed list
    put the starting node on the open list (you can leave its f at zero)
    
    while the open list is not empty
        find the node with the least f on the open list, call it "q"
        pop q off the open list
        generate q's 8 successors and set their parents to q
        for each successor
        	if successor is the goal, stop the search
            successor.g = q.g + distance between successor and q
            successor.h = distance from goal to successor
            successor.f = successor.g + successor.h
    
            if a node with the same position as successor is in the OPEN list \
                which has a lower f than successor, skip this successor
            if a node with the same position as successor is in the CLOSED list \ 
                which has a lower f than successor, skip this successor
            otherwise, add the node to the open list
        end
        push q on the closed list
    end 
    

    In that way, we only add a node to the queue if it guarantees a better solution.


  • 0
    M

    @wufangjie Could you explain the meanings of add1,add2,stack1,stack2?


  • 0

    (Edit: It's fixed now)

    I found a small bug: For example for input [[2, 1]] you return 2 instead of 0. It's because you mishandle "ground" cells anywhere except at position (0, 0). Sadly the whole test suite doesn't contain ground cells at any other positions.


  • 0
    W

    @StefanPochmann you are right, thank you for pointing out that. I have fixed it. And I want to say something which other one may not notice, there will be many ground cells.


  • 0

    @wufangjie said in my python solution, inspired by A* algorithm:

    And I want to say something which other one may not notice, there will be many ground cells.

    Sorry, I don't understand what you mean. Can you rephrase that?


  • 0
    W

    @mainarke add1 and stack1 means the current best strategy, if we walk through the positions in stack1, which added by add1, we can expect to get the min distance. On the other hand, if stack1 is empty, it means all the min distance way are blocked, so we have to take the suboptimal strategy which will make the min distance +2, add2 and stack2 is for that. And then recursive. Sorry for my poor English and explanation.


  • 0
    W

    @StefanPochmann the Description says "You are guaranteed that no two trees have the same height ", so I think [[0, 2, 1, 1, 1]] is allowed


  • 0

    @wufangjie Ah, ok. You meant there can be many ground cells. Yes, I agree that that's allowed.


Log in to reply
 

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