day25_417_2.py

fromtypingimportList, Set, Tuple


classSolution:
defpacificAtlantic(self, heights: List[List[int]]) ->List[List[int]]:
"""要求既可流向太平洋也可流向大西洋
 遍历每个边界坐标，深度优先搜索到的点添加，并交集表示即可到达太平洋，又可达大西洋
 """
iflen(heights) ==0orlen(heights[0]) ==0:
raiseKeyError
rows, cols=len(heights), len(heights[0])
border_p= [(0, index) forindexinrange(cols)] + [(index, 0) forindexinrange(rows)]
border_a= [(rows-1, index) forindexinrange(cols)] + [(index, cols-1) forindexinrange(rows)]
returnlist(map(list, self.search(border_p, heights) &self.search(border_a, heights)))

defsearch(self, starts, heights) ->Set[Tuple[int, int]]:
visit=set()
rows, cols=len(heights), len(heights[0])
forrow, colinstarts:
self.dfs(row, col, rows, cols, visit, heights)
returnvisit

defdfs(self, row, col, rows, cols, visit, heights):
if (row, col) invisit:
return
visit.add((row, col))
fordirectin [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nrow, ncol=row+direct[0], col+direct[1]
if0<=nrow<rowsand0<=ncol<colsandheights[nrow][ncol] >=heights[row][col]:
self.dfs(nrow, ncol, rows, cols, visit, heights)


if__name__=="__main__":
ans=Solution().pacificAtlantic(
heights=[
 [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],
 ]
 )
assertsorted(ans) ==sorted([[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]])
ans=Solution().pacificAtlantic(heights=[[2, 1], [1, 2]])
assertsorted(ans) ==sorted([[0, 0], [0, 1], [1, 0], [1, 1]])