Untitled
unknown
python
a year ago
1.4 kB
41
Indexable
Never
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$$$$ '''