from itertools import product


class Solution(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        # original idea by @ts, who won the contest with this problem
        if len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0
        m, n = len(heightMap), len(heightMap[0])
        queue, level = set(), [[float('+inf')] * n for __ in xrange(m)]
        for i in xrange(m):
            queue |= {(i, 0), (i, n - 1)}
            level[i][0] = heightMap[i][0]
            level[i][n - 1] = heightMap[i][n - 1]
        for j in xrange(1, n - 1):
            queue |= {(0, j), (m - 1, j)}
            level[0][j] = heightMap[0][j]
            level[m - 1][j] = heightMap[m - 1][j]

        def within(i, j):
            return 0 <= i < m and 0 <= j < n

        nearby = ((0, -1), (0, +1), (-1, 0), (+1, 0))
        next_queue = set()
        while queue:
            for i, j in queue:
                for di, dj in nearby:
                    if within(i + di, j + dj):
                        new_level = max(level[i][j], heightMap[i + di][j + dj])
                        if new_level < level[i + di][j + dj]:
                            level[i + di][j + dj] = new_level
                            next_queue.add((i + di, j + dj))
            queue = next_queue
            next_queue = set()
        return sum(level[i][j] - heightMap[i][j]
                   for i, j in product(xrange(m), xrange(n)))

    def trapRainWater_fh(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        # original idea by @lixx2100, Fibonacci Heap implementation mine

        class FibonacciNode:
            def __init__(self, value):
                self.value = value
                self.next = self.prev = self
                self.child = self.parent = None
                self.marked = False
                self.degree = 0

            def append(self, next):
                old_next = self.next
                self.next = next
                next.next = old_next
                next.prev = self
                old_next.prev = next

            def add_child(self, child):
                if not self.child:
                    self.child = child
                    child.next = child.prev = child
                else:
                    self.child.append(child)
                child.parent = self
                self.degree += 1

            def remove_child(self, child):
                if child.prev is child:
                    self.child = None
                else:
                    child.next.prev = child.prev
                    child.prev.next = child.next
                    if self.child is child:
                        self.child = child.next
                    child.prev = child.next = child
                child.parent = None
                self.degree -= 1

            def dump(self, indent):
                assert self.value not in dumped
                dumped.add(self.value)
                print ' ' * indent, self.value, self.degree
                if self.child:
                    node = self.child
                    while True:
                        node.dump(indent + 4)
                        node = node.next
                        if node is self.child:
                            break

        class NodesByDegree:
            def __init__(self):
                self.nodes = {}

            def insert(self, node):
                if node.degree not in self.nodes:
                    self.nodes[node.degree] = node
                else:
                    old_node = self.nodes[node.degree]
                    del self.nodes[node.degree]
                    if old_node.value <= node.value:
                        new_node = old_node
                        new_node.add_child(node)
                    else:
                        new_node = node
                        node.add_child(old_node)
                    self.insert(new_node)

            def __iter__(self):
                return self.nodes.itervalues()

        class FibonacciHeap:

            def __init__(self):
                self.head = None

            def __nonzero__(self):
                return bool(self.head)

            def insert(self, value):
                node = FibonacciNode(value)
                if self.head:
                    self.head.append(node)
                    if node.value < self.head.value:
                        self.head = node
                else:
                    self.head = node
                return node

            def peek(self):
                return self.head

            def pop(self):
                roots = NodesByDegree()
                count = 0
                # insert roots except head (min)
                node = self.head.next
                while node is not self.head:
                    next = node.next
                    count += 1
                    roots.insert(node)
                    node = next
                if self.head.child:
                    # insert head's children
                    node = self.head.child
                    while True:
                        next = node.next
                        count += 1
                        roots.insert(node)
                        node = next
                        if node is self.head.child:
                            break
                node = self.head
                # link the new roots back into a linked list
                self.head = None
                for root in roots:
                    self.append_root(root)
                if count > 30:
                    print count
                return node

            def append_root(self, root):
                root.parent = None
                root.marked = False
                if not self.head:
                    self.head = root
                    root.next = root.prev = root
                else:
                    self.head.append(root)
                    if root.value < self.head.value:
                        self.head = root

            def decrease(self, node, value):
                node.value = value
                if not node.parent:
                    if node.value < self.head.value:
                        self.head = node
                elif node.value < node.parent.value:
                    self.mark_or_cut(node.parent)
                    node.parent.remove_child(node)
                    self.append_root(node)

            def mark_or_cut(self, node):
                if node.marked:
                    if node.parent:
                        self.mark_or_cut(node.parent)
                        node.parent.remove_child(node)
                    self.append_root(node)
                elif node.parent:
                    node.marked = True

            def dump(self):
                dumped.clear()
                node = self.head
                while True:
                    node.dump(0)
                    node = node.next
                    if node is self.head:
                        break

        dumped = set()
        if len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0

        def within(i, j):
            return 0 <= i < m and 0 <= j < n

        m, n = len(heightMap), len(heightMap[0])
        nearby = ((0, -1), (0, +1), (-1, 0), (+1, 0))
        fh = FibonacciHeap()
        level = [[None] * n for __ in xrange(m)]
        # the starting virtual "node" is the outside world
        for i in xrange(m):
            for j in xrange(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    value = heightMap[i][j], i, j
                else:
                    value = float('+inf'), i, j
                level[i][j] = fh.insert(value)
        while fh:
            h, i, j = fh.pop().value
            for di, dj in nearby:
                if within(i + di, j + dj):
                    new_high = max(h, heightMap[i + di][j + dj])
                    if new_high < level[i + di][j + dj].value[0]:
                        fh.decrease(level[i + di][j + dj], (new_high, i + di, j + dj))
        return sum(level[i][j].value[0] - heightMap[i][j]
                   for i, j in product(xrange(m), xrange(n)))
