# Time:  O(t * (logt + m * n)), t is the number of trees
# Space: O(t + m * n)

# You are asked to cut off trees in a forest for a golf event.
# The forest is represented as a non-negative 2D map, in this map:
#
# 0 represents the obstacle can't be reached.
# 1 represents the ground can be walked through.
# The place with number bigger than 1 represents a tree can be walked through,
# and this positive number represents the tree's height.
#
# You are asked to cut off all the trees in this forest in the order of tree's height -
# always cut off the tree with lowest height first. And after cutting, the original place
# has the tree will become a grass (value 1).
#
# You will start from the point (0, 0)
# and you should output the minimum steps you need to walk to cut off all the trees.
# If you can't cut off all the trees, output -1 in that situation.
#
# You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.
#
# Example 1:
# Input: 
# [
#  [1,2,3],
#  [0,0,4],
#  [7,6,5]
# ]
# Output: 6
# Example 2:
# Input: 
# [
#  [1,2,3],
#  [0,0,0],
#  [7,6,5]
# ]
# Output: -1
# Example 3:
# Input: 
# [
#  [2,3,4],
#  [0,0,5],
#  [8,7,6]
# ]
# Output: 6
# Explanation: You started from the point (0,0) and you can cut off the tree
# in (0,0) directly without walking.
# Hint: size of the given matrix will not exceed 50x50.

# Reference: https://discuss.leetcode.com/topic/103532/my-python-solution-inspired-by-a-algorithm/2
class Solution(object):
    def cutOffTree(self, forest):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        def minStep(p1, p2):
            min_steps = abs(p1[0]-p2[0])+abs(p1[1]-p2[1])
            stack1, stack2 = [p1], []
            used, visited = {p1}, {p1}

            while True:
                if not stack1:
                    stack1, stack2 = stack2, stack1
                    used.update(stack1)
                    min_steps += 2

                if not stack1:
                    return -1

                (i, j) = stack1.pop()
                if (i, j) == p2:
                    break

                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 (i, j) in add1:
                    if 0 <= i < m and 0 <= j < n and forest[i][j] and (i, j) not in used:
                        visited.add((i, j))
                        stack1.append((i, j))
                        used.add((i, j))
                for (i, j) in add2:
                    if 0 <= i < m and 0 <= j < n and forest[i][j] and (i, j) not in visited:
                        visited.add((i, j))
                        stack2.append((i, j))

            return min_steps

        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        m, n = len(forest), len(forest[0])
        min_heap = []
        for i in xrange(m):
            for j in xrange(n):
                if forest[i][j] > 1:
                    heapq.heappush(min_heap, (forest[i][j], (i, j)))

        start = (0, 0)
        result = 0
        while min_heap:
            tree = heapq.heappop(min_heap)
            step = minStep(start, tree[1])
            if step < 0:
                return -1
            result += step
            start = tree[1]
        return result


# Time:  O(t * (logt + m * n)), t is the number of trees
# Space: O(t + m * n)
class Solution_TLE(object):
    def cutOffTree(self, forest):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        def minStep(p1, p2):
            step = 0
            used = set()
            q = collections.deque()
            q.append(p1);
            used.add(start)
            while q:
                size = len(q)
                for _ in xrange(size):
                    (i, j) = q.popleft()
                    if (i, j) == p2:
                        return step
                    for direction in directions:
                        ii, jj = i+direction[0], j+direction[1]
                        if not (0 <= ii < m and 0 <= jj < n and forest[ii][jj] and (ii, jj) not in used):
                            continue
                        q.append((ii, jj))
                        used.add((ii, jj))
                step += 1
            return -1
        
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        m, n = len(forest), len(forest[0])
        min_heap = []
        for i in xrange(m):
            for j in xrange(n):
                if forest[i][j] > 1:
                    heapq.heappush(min_heap, (forest[i][j], (i, j)))

        start = (0, 0)
        result = 0
        while min_heap:
            tree = heapq.heappop(min_heap)
            step = minStep(start, tree[1])
            if step < 0:
                return -1
            result += step
            start = tree[1]
        return result

@@ -4178,20 +4178,25 @@
         
+min_
 step
+s
  = 0%0A   
@@ -4215,13 +4215,12 @@
 d = 
-set()
+%7Bp1%7D
 %0A   
@@ -4254,62 +4254,12 @@
 que(
-)%0A            q.append(p1);%0A            used.add(start
+%5Bp1%5D
 )%0A  
@@ -4455,20 +4455,25 @@
  return 
+min_
 step
+s
 %0A       
@@ -4823,20 +4823,25 @@
         
+min_
 step
+s
  += 1%0A  

Update cut-off-trees-for-golf-event.py