[Python] simple bfs, explained
Let us reverse logic in this problem. Instead of looking for places from which one or another ocean can be reached, we will start from ocean and move in increas
Let us reverse logic in this problem. Instead of looking for places from which one or another ocean can be reached, we will start from ocean and move in **increasing** way, not decreasing. So, we do the following\n1. Start from `pacific` ocean: all nodes with one of coordinates equal to `0`, and perform `bfs` from all these cells: we put them into queue and then as usual popleft element and add its neigbours if we can: that is we did not visit it yet, and such that new value is more or equal to the old one. In the end my function return all visited cells.\n2. Start from `atlantic` ocean and do exactly the same logic.\n3. Finally, intersect two sets we get on previous two steps and return it (even though it is set, not list, leetcode allows to do it)\n\n**Complexity**: time and space complexity is `O(mn)`: we perform bfs twice and then did intersection of sets.\n\n```\nclass Solution:\n    def pacificAtlantic(self, M):\n        if not M or not M[0]: return []\n        \n        m, n = len(M[0]), len(M)\n        def bfs(starts):\n            queue = deque(starts)\n            visited = set(starts)\n            while queue:\n                x, y = queue.popleft()\n                for dx, dy in [(x, y+1), (x, y-1), (x-1, y), (x+1, y)]:\n                    if 0 <= dx < n and 0 <= dy < m and (dx, dy) not in visited and M[dx][dy] >= M[x][y]:\n                        queue.append((dx, dy))\n                        visited.add((dx, dy))\n                        \n            return visited\n        \n        pacific  = [(0, i) for i in range(m)]   + [(i, 0) for i in range(1,n)]\n        atlantic = [(n-1, i) for i in range(m)] + [(i, m-1) for i in range(n-1)]\n        \n        return bfs(pacific) & bfs(atlantic)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Breadth-First Search']