Untitled

mx = [-1, 0, 1, 0]
my = [0, -1, 0, 1]

class Solution(object):
    def pacificAtlantic(self, heights):
        self.n = len(heights)
        self.m = len(heights[0])

        ps1 = set()
        for i in xrange(self.n):
            ps1.add((i, 0))
        for i in xrange(self.m):
            ps1.add((0, i))

        st1 = self.solve(heights, ps1)

        ps2 = set()
        for i in xrange(self.n):
            ps2.add((i, self.m - 1))
        for i in xrange(self.m):
            ps2.add((self.n - 1, i))

        st2 = self.solve(heights, ps2)

        return sorted(st1 & st2)
        
    def solve(self, heights, st):
        q = list(st)
        while q:
            y, x = q.pop(0)
            h = heights[y][x]

            for i in xrange(4):
                ny = y + my[i]
                nx = x + mx[i]
                if 0 <= ny < self.n and 0 <= nx < self.m:
                    nh = heights[ny][nx]
                    if nh >= h:
                        if (ny, nx) not in st:
                            q.append((ny, nx))
                            st.add((ny, nx))
        return st

'''
^^^^^TEST^^^^^
[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
----------
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
$$$$TEST$$$$

^^^^^TEST^^^^^
[[1]]
--------
[[0,0]]
$$$$TEST$$$$
'''