Python DFS bests 85%. Tips for all DFS in matrix question.
The DFS solution is straightforward. Starting from each point, and dfs its neighbor if the neighbor is equal or less than itself. And maintain two boolean matri
The DFS solution is straightforward. Starting from each point, and dfs its neighbor if the neighbor is equal or less than itself. And maintain two boolean matrix for two oceans, indicating an ocean can reach to that point or not. Finally go through all nodes again and see if it can be both reached by two oceans. The trick is if a node is already visited, no need to visited again. Otherwise it will reach the recursion limits.\n\nThis question is very similar to https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ And here are some common tips for this kind of question\n1. init a directions var like `self.directions = [(1,0),(-1,0),(0,1),(0,-1)]` so that when you want to explore from a node, you can just do \n```\nfor direction in self.directions:\n            x, y = i + direction[0], j + direction[1]\n```\n\n2. this is a what I normally do for a dfs helper method for exploring a matrix\n```\ndef dfs(self, i, j, matrix, visited, m, n):\n  if visited: \n    # return or return a value\n  for dir in self.directions:\n    x, y = i + direction[0], j + direction[1]\n        if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j] (or a condition you want to skip this round):\n           continue\n        # do something like\n        visited[i][j] = True\n        # explore the next level like\n        self.dfs(x, y, matrix, visited, m, n)\n```\nHope it helps\n\n*Solution*\n```\nclass Solution(object):\n    def pacificAtlantic(self, matrix):\n        """\n        :type matrix: List[List[int]]\n        :rtype: List[List[int]]\n        """\n        if not matrix: return []\n        self.directions = [(1,0),(-1,0),(0,1),(0,-1)]\n        m = len(matrix)\n        n = len(matrix[0])\n        p_visited = [[False for _ in range(n)] for _ in range(m)]\n        \n        a_visited = [[False for _ in range(n)] for _ in range(m)]\n        result = []\n        \n        for i in range(m):\n            # p_visited[i][0] = True\n            # a_visited[i][n-1] = True\n            self.dfs(matrix, i, 0, p_visited, m, n)\n            self.dfs(matrix, i, n-1, a_visited, m, n)\n        for j in range(n):\n            # p_visited[0][j] = True\n            # a_visited[m-1][j] = True\n            self.dfs(matrix, 0, j, p_visited, m, n)\n            self.dfs(matrix, m-1, j, a_visited, m, n)\n            \n        for i in range(m):\n            for j in range(n):\n                if p_visited[i][j] and a_visited[i][j]:\n                    result.append([i,j])\n        return result\n                \n                \n    def dfs(self, matrix, i, j, visited, m, n):\n        # when dfs called, meaning its caller already verified this point \n        visited[i][j] = True\n        for dir in self.directions:\n            x, y = i + dir[0], j + dir[1]\n            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:\n                continue\n            self.dfs(matrix, x, y, visited, m, n)\n# 113 / 113 test cases passed.\n# Runtime: 196 ms\n```\n\n*Solution for longest increasing path in matrix*\n```\nclass Solution(object):\n    def longestIncreasingPath(self, matrix):\n        """\n        :type matrix: List[List[int]]\n        :rtype: int\n        """\n        if not matrix: return 0\n        self.directions = [(1,0),(-1,0),(0,1),(0,-1)]\n        m = len(matrix)\n        n = len(matrix[0])\n        cache = [[-1 for _ in range(n)] for _ in range(m)]\n        res = 0\n        for i in range(m):\n            for j in range(n):\n                cur_len = self.dfs(i, j, matrix, cache, m, n)\n                res = max(res, cur_len)\n        return res\n        \n    def dfs(self, i, j, matrix, cache, m, n):\n        if cache[i][j] != -1:\n            return cache[i][j]\n        res = 1\n        for direction in self.directions:\n            x, y = i + direction[0], j + direction[1]\n            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j]:\n                continue\n            length = 1 + self.dfs(x, y, matrix, cache, m, n)\n            res = max(length, res)\n        cache[i][j] = res\n        return res\n```
[]