太平洋大西洋水流问题

太平洋大西洋水流问题

九月 02, 2021

太平洋大西洋水流问题

这道题本来打算每一个方格都遍历一遍然后依次查找比自己小的相邻数并标记然后不断重复 后来觉得太麻烦 于是想到从海往上 从小到大的话可以省去许多重复的步骤 建立两个数组 标记水流都能到达的地方为true 然后两个数组都为true的地方便是结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def pacificAtlantic(self, heights):
        m=len(heights)
        n=len(heights[0])
        ocean_one=[[False for _ in range(n)] for _ in range(m) ]
        ocean_two=[[False for _ in range(n)] for _ in range(m) ]
        res=[]
        directions = [[0,1], [0,-1], [1, 0], [-1,0]]
        def dfs(martix,i,j):
            martix[i][j]=True
            for direction in directions:
                x=i+direction[0]
                y=j+direction[1]
                if 0<=x<m and 0<=y<n and heights[i][j]<=heights[x][y] and not martix[x][y]:
                    dfs(martix,x,y)
        for index in range(m):
            dfs(ocean_one,index,0) 
            dfs(ocean_two,index,n-1)
        for index in range(n):
            dfs(ocean_one,0,index)
            dfs(ocean_two,m-1,index)
        for i in range(m):
            for j in range(n):
                if ocean_one[i][j] and ocean_two[i][j]:
                    res.append([i,j])
        return res