LeetCode0417.PacificAtlanticWaterFlow太平洋大洋水流问题【Medium】【Python】【DFS】ProblemLeetCodeGivenananheightoftheeachnon-negativemxnsmatrixoftheeachnon-negativemxnsmatrixofthe大陆中的晶胞，“太平洋”触及矩阵的左边缘和上边缘，“大西洋”触及矩阵的右边缘和下边缘。水只能沿四个方向流动（上、下、左或右）从一个单元格到另一个高度等于或更低的单元格。找到水可以流向太平洋和大西洋的网格坐标列表。注意：返回的网格坐标的顺序无关紧要。m和n都小于150.示例：给定以下5x5矩阵：Pacific~~~~~1223(5)*~323(4)(4)*~24(5)31*~(6)(7)145*~(5)1124******AtlanticReturn:[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]（上述矩阵中带括号的位置）。该问题给定一个mxn的非负整数矩阵来表示大陆上每个单元格的高度。“太平洋”在大陆的左上边界，“大西洋”在大陆的右下边界。规定水流只能向上、下、左、右四个方向流动，只能由高向低或同一高度流动。找到水同时流入“太平洋”和“大西洋”的那些陆地像元的坐标。提示：输出坐标的顺序并不重要m和n均小于150示例：给定以下5x5矩阵：Pacific~~~~~1223(5)*~323(4)(4)*~24(5)31*~(6)(7)145*~(5)1124******大西洋返回：[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]（上图中带括号的单位）。DFS的思想是从边界开始遍历，找到水可以流动的位置。因为是倒过来的，应该满足[x,y]>[i,j]，即[x,y]应该高于[i,j]。时间复杂度：O(m*n)空间复杂度：O(m*n)Python3代码类解决方案：defpacificAtlantic(self,matrix:List[List[int]])->List[List[int]]:ifnotmatrixornotmatrix[0]:return[]m,n=len(matrix),len(matrix[0])p_visited=[[False]*nforxinrange(m)]#Pacifica_visited=[[False]*nforxinrange(m)]#Atlantic#leftandrightforiinrange(m):self.dfs(p_visited,matrix,m,n,i,0)self.dfs(a_visited,matrix,m,n,i,n-1)#upanddownforjinrange(n):self.dfs(p_visited,matrix,m,n,0,j)self.dfs(a_visited,matrix,m,n,m-1,j)ans=[]foriinrange(m):forjinrange(n):如果p_visited[i][j]anda_visited[i][j]:ans.append([i,j])返回ansdefdfs(self,visited,matrix,m,n,i,j):visited[i][j]=Truedirections=[(-1,0),(0,1),(1,0),(0,-1)]对于方向上的d：x,y=i+d[0],j+d[1]如果x<0orx>=mory<0ory>=norvisited[x][y]ormatrix[x][y]
