class MarixCallBack():
    def __init__(self, matrix, size, triger):
        self._triger = triger
        self._row, self._col = size

        self._matri = matrix
        self._directions = [(1,0),(-1,0),(0,1),(0,-1)]
        
        self._funcs = dict()
        self._flags = set()
        
        for i in range(self._row):
            for j in range(self._col):
                self._funcs[(i, j)] = set()
    
    def Add(self, coordinate):
        x, y = coordinate
        if x == self._triger[0] or y == self._triger[1]:
            self.Set(coordinate)
            return

        for direction in self._directions:
            _x = x + direction[0]
            _y = y + direction[1]
            if _x > -1 and _x < self._row and _y > -1 and _y < self._col \
                        and self._matri[_x][_y] <= self._matri[x][y]:
                if (_x, _y) in self._flags:
                    self.Set(coordinate)
                    return
                else:
                    '''when shift has value, then call origin coordinate'''
                    self._funcs[(_x, _y)].add(coordinate)

    def Set(self, coordinate):
        if coordinate in self._flags:
            return
        self._flags.add(coordinate)
        while self._funcs[coordinate]:
            self.Set(self._funcs[coordinate].pop())

class Solution(object):
    def pacificAtlantic(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        
        PA = MarixCallBack(matrix, (m, n), (0, 0))
        AT = MarixCallBack(matrix, (m, n), (m-1, n-1))
        
        for i in range(m):
            for j in range(n):
                PA.Add((i, j))
                AT.Add((i, j))
        
        return list(AT._flags & PA._flags)

class MarixDeepFirstSearch():
    def __init__(self, matrix, size):
        self._row, self._col = size
        self._matri = matrix
        self._directions = [(1,0),(-1,0),(0,1),(0,-1)]
        self._added = set()

    def Add(self, coordinate):
        self._added.add(coordinate)
        x, y = coordinate
        for direction in self._directions:
            _x = x + direction[0]
            _y = y + direction[1]
            if _x > -1 and _x < self._row and _y > -1 and _y < self._col \
                and self._matri[_x][_y] >= self._matri[x][y] \
                and (_x, _y) not in self._added:
                    '''Add larger coordinate'''
                    self.Add((_x, _y))

class Solution(object):
    def pacificAtlantic(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        if not matrix:
            return []
            
        m, n = len(matrix), len(matrix[0])
        PA = MarixDeepFirstSearch(matrix, (m,n))
        AT = MarixDeepFirstSearch(matrix, (m,n))
        
        for i in range(m):
            PA.Add((i,   0))
            AT.Add((i,   n-1))
        for j in range(n):
            PA.Add((0,   j)) 
            AT.Add((m-1, j))
        
        return list(PA._added & AT._added)