太平洋大西洋水流问题

这道题只能写逆流！！顺流试了好几次内存都不够，所以只能从海洋出发，然后看那些地方是可以达到的，这是见过的第二个逆流问题了，上一题是130题。
写法上这个dfs没有return，所以就是其实回溯不需要明确的终止，如果需要的话走完也可以。

class Solution:def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:def dfs(i,j,matrix):matrix[i][j] = True for k1,k2 in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:if (0 <= k1 < m and 0 <= k2 < n) and matrix[k1][k2] == True: continueif (0 <= k1 < m and 0 <= k2 < n) and heights[k1][k2] >=  heights[i][j]:dfs(k1,k2,matrix)m = len(heights)n = len(heights[0])Pa = [[False]*n for _ in range(m)]At = [[False]*n for _ in range(m)]res = []for i in range(m):dfs(i,0,Pa)dfs(i,n-1,At)for j in range(n):dfs(0,j,Pa)dfs(m-1,j,At)for i in range(m):for j in range(n):if Pa[i][j] and At[i][j]:res.append([i,j])return res

飞地的数量

和130是一样的题，也是从外到里比较好做。

class Solution:def numEnclaves(self, grid: List[List[int]]) -> int:def dfs(i,j):grid[i][j] = 0for k1,k2 in [[i-1,j],[i+1,j],[i,j+1],[i,j-1]]:if (0 <= k1 < m and 0<= k2 < n) and grid[k1][k2] == 1:dfs(k1,k2)m = len(grid)n = len(grid[0])for i in range(m):if grid[i][0] == 1: dfs(i,0)if grid[i][n-1] == 1: dfs(i,n-1)for j in range(n):if grid[0][j] == 1: dfs(0,j)if grid[m-1][j] == 1: dfs(m-1,j)return sum(sum(grid[i]) for i in range(m))

统计封闭岛屿的数目

一样的问题顺手做了，我这里的思路就是先把没有被包围的岛（0）转成水（1），然后再去找被包围的岛。

class Solution:def closedIsland(self, grid: List[List[int]]) -> int:def dfs(i,j):grid[i][j] = 1for k1,k2 in [[i-1,j],[i+1,j],[i,j+1],[i,j-1]]:if (0 <= k1 < m and 0<= k2 < n) and grid[k1][k2] == 0:dfs(k1,k2)m = len(grid)n = len(grid[0])for i in range(m):if grid[i][0] == 0: dfs(i,0)if grid[i][n-1] == 0: dfs(i,n-1)for j in range(n):if grid[0][j] == 0: dfs(0,j)if grid[m-1][j] == 0: dfs(m-1,j)#print(grid)res = 0for i in range(m):for j in range(n):if grid[i][j] == 0:dfs(i,j)res += 1return res