岛屿问题 中等：130、1020、1254、200、695、16 130,1020题意大致一样，1254和200题型一样，但200默认被水包围，少一个边界判定条件。695吗6,19岛屿的面积题型一样。
困难：827、778、417、934、749
地图问题 中等：offer13.offer12 12寻找单词，

中等

剑指 Offer 13. 机器人的运动范围

地图问题 - 图2
思路：将方格值全部设置为1，把数位和满足要求的设置为0，然后从0开始遍历，遍历过的设置为1，以防重复计算。

  1. class Solution:
  2.     def movingCount(self, m: int, n: int, k: int) -> int:
  3.         visited = [[1] * n for _ in range(m)]
  4.         for i in range(m):
  5.             for j in range(n):
  6.                 # 可抵达节点设置为0
  7.                 if i // 10 + i % 10 + j // 10 + j % 10 <= k:   # 注意，题里只包括两位数
  8.                     visited[i][j] = 0
  10.         def dfs(x, y):
  11.             if x < 0 or x >= m or y < 0 or y >= n or visited[x][y]:   # 超出数组范围或者已访问过
  12.                 return 0
  13.             visited[x][y] = 1
  14.             return 1 + dfs(x + 1, y) + dfs(x, y + 1)
  16.         return dfs(0, 0)
  1. class Solution:
  2.     def movingCount(self, m: int, n: int, k: int) -> int:
  3.         visited = [[1] * n for _ in range(m)]
  4.         for i in range(m):
  5.             for j in range(n):
  6.                 if i // 10 + i % 10 + j // 10 + j % 10 <= k:
  7.                     visited[i][j] = 0
  9.         queue = collections.deque([(0, 0)])
  10.         res = 0
  11.         while queue:
  12.             x, y = queue.popleft()
  13.             res += 1
  14.             for dx, dy in ((1, 0), (0, 1)):
  15.                 nx, ny = x + dx, y + dy
  16.                 if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
  17.                     visited[nx][ny] = 1
  18.                     queue.append((nx, ny))
  19.         return res

√剑指 Offer 12. 矩阵中的路径

image.png

  1. class Solution:
  2.     def exist(self, board: List[List[str]], word: str) -> bool:
  3.         def dfs(i,j,w):
  4.             if w==len(word):
  5.                 return True
  6.             for d in [[-1,0],[0,1],[1,0],[0,-1]]:
  7.                 ni=i+d[0]
  8.                 nj=j+d[1]
  9.                 if 0<=ni<m and 0<=nj<n and board[ni][nj]==word[w]:
  10.                     tmp=board[i][j]    
  11.                     board[i][j]='0'    # 防止重复访问
  12.                     if dfs(ni,nj,w+1):   # 注意，这里要加判断跳出循环。
  13.                         return True
  14.                     board[i][j]=tmp    # 恢复
  15.             # print(board)
  16.             return False
  18.         m=len(board)
  19.         n=len(board[0])
  20.         for i in range(m):
  21.             for j in range(n):
  22.                 if board[i][j]==word[0]:
  23.                     board[i][j] = '0'
  24.                     if dfs(i, j, 1):
  25.                         return True
  26.                     board[i][j] = word[0]
  27.         return False

√130.被围绕的区域

image.png
image.png
先边界DFS，找出不被围绕的区域（和1020相同），将它复制为B，之后将O换成X，将B换回O

  1. class Solution:
  2.     def solve(self, board: List[List[str]]) -> None:
  3.         """
  4.         Do not return anything, modify board in-place instead.
  5.         """
  6.         len_x = len(board)
  7.         len_y = len(board[0])
  9.         def dfs(x, y):
  10.             board[x][y] = 'B'   # 注意，与边界相连的都可以离开
  11.             directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
  12.             for _x, _y in directions:
  13.                 dx,dy=x + _x,y+_y
  14.                 if dx >= 0 and dx < len_x and dy >= 0 and dy < len_y and board[dx][dy]=='O' :
  15.                     dfs(dx, dy)
  16.         for i in range(len_x):
  17.             for j in range(len_y): 
  18.                 if (i in [0, len_x - 1] or j in [0, len_y - 1]) and board[i][j]=='O':   #注意边界DFS
  19.                     dfs(i,j)
  20.         for i in range(len_x):
  21.             for j in range(len_y): 
  22.                 if board[i][j]=='O':
  23.                     board[i][j]='X'
  24.                 elif board[i][j]=='B':
  25.                     board[i][j]='O'

√1020.飞地的数量(边界DFS)

image.png

  1. class Solution:
  2.     def numEnclaves(self, A: List[List[int]]) -> int:
  3.         if not A:
  4.             return 0
  5.         len_x = len(A)
  6.         len_y = len(A[0])
  8.         def dfs(x, y):
  9.             A[x][y] = 0   # 注意，与边界相连的都可以离开
  10.             directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
  11.             for _x, _y in directions:
  12.                 dx,dy=x + _x,y+_y
  13.                 if dx >= 0 and dx < len_x and dy >= 0 and dy < len_y and A[dx][dy] :
  14.                     dfs(dx, dy)
  15.         for i in range(len_x):
  16.             for j in range(len_y): 
  17.                 if (i in [0, len_x - 1] or j in [0, len_y - 1]) and A[i][j]:   #注意边界DFS
  18.                     dfs(i,j)
  19.         return sum([sum(A[i]) for i in range(len_x)])

√1254.统计封闭岛屿的数目（flag记录）

image.png
image.png
(这里DFS也可以结合695返回值为1 ，FLAG为TRUE时加上这个数，就代表1020无法离开的数量)

  1. class Solution:
  2.     def closedIsland(self, grid: List[List[int]]) -> int:
  3.         m, n = len(grid), len(grid[0])
  4.         def dfs(i, j):
  5.             grid[i][j] = 1   # 注意，防止重复遍历
  6.             for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
  7.                 x, y = i + di, j + dj
  8.                 if 0 <= x < m and 0 <= y < n and grid[x][y]==0:
  9.                     dfs(x, y)
  10.                 else:   # 注意，如果到达边界， 说明不封闭。
  11.                     nonlocal flag    # 使它能够修变量
  12.                     flag = False
  13.         ans = 0
  14.         for i, j in itertools.product(range(m), range(n)):
  15.             flag = True
  16.             if not grid[i][j]:
  17.                 dfs(i, j)
  18.                 ans += flag
  19.         return ans

√200.岛屿数量

image.png

不用考虑边界条件,这里是字符不是数字

  1. class Solution:
  2.     def numIslands(self, grid: List[List[str]]) -> int:
  3.         m, n = len(grid), len(grid[0])
  4.         def dfs(x, y):
  5.             grid[x][y] = '0'   # 注意，防止重复遍历
  6.             for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
  7.                 dx, dy = x + di, y + dj
  8.                 if 0 <= dx < m and 0 <= dy < n and grid[dx][dy]=='1':
  9.                     dfs(dx, dy)
  10.         ans = 0
  11.         for i, j in itertools.product(range(m), range(n)):
  12.             if grid[i][j]=='1':
  13.                 dfs(i, j)
  14.                 ans += 1
  15.         return ans

√695.岛屿的最大面积（计算DFS遍历了多少个节点）

image.png
image.png
可以根据下一题，返回数组最后一个数，但要注意为了防止数组为空，需要初始化rst=[0],return res[-1] ,另一种解法就是拿一个变量记录当前值，然后和前一个值对比取最大值。没有排序时间上会更快一点。
image.png

  1. class Solution:
  2.     def maxAreaOfIsland(self, land: List[List[int]]) -> int:
  3.         n = len(land)
  4.         m = len(land[0])
  5.         ans = 0   # 给一个初始值，防止数组为空
  6.         def dfs(i,j):
  7.             land[i][j]=0
  8.             area = 1
  9.             for (dx,dy) in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
  10.                 if dx>=0 and dx<n and dy>=0 and dy<m and land[dx][dy]==1:
  11.                     area+=dfs(dx,dy)
  12.             return area
  14.         for i in range(n):
  15.             for j in range(m):
  16.                 if land[i][j]==1:
  17.                     num=dfs(i,j)   # 注意
  18.                     ans=max(ans,num)       # 注意 
  19.         return ans

√16.19水域大小 （排序）

image.png

  1. class Solution:
  2.     def pondSizes(self, land: List[List[int]]) -> List[int]:
  3.         n = len(land)
  4.         m = len(land[0])
  5.         rst = []
  6.         def dfs(i,j):
  7.             land[i][j]=1 
  8.             area = 1    # 注意
  9.             for (dx,dy) in [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)]:
  10.                 if dx>=0 and dx<n and dy>=0 and dy<m and land[dx][dy]==0:
  11.                     area+=dfs(dx,dy)   # 注意
  12.             return area    # 注意
  14.         for i in range(n):
  15.             for j in range(m):
  16.                 if land[i][j]==0:
  17.                     rst.append(dfs(i,j))      
  18.         rst.sort()
  19.         return rst

困难

√827.最大人工岛

image.png

重新赋值为岛屿面积，对0点遍历

将每个岛屿进行重新赋值，利用哈希表存储岛屿对应的数值和面积。然后对0点四周进行遍历，相邻岛屿面积相加。最后比较最大值

  1. class Solution:
  2.     def largestIsland(self, grid: List[List[int]]) -> int:
  3.         def dfs(i,j,grid,newnumber):
  4.             if i<0 or i>m-1 or j<0 or j>n-1:
  5.                 return 0
  6.             if grid[i][j] != 1:
  7.                 return 0
  8.             grid[i][j] = newnumber
  9.             return 1+dfs(i-1,j,grid,newnumber)+dfs(i,j-1,grid,newnumber)+dfs(i+1,j,grid,newnumber)+dfs(i,j+1,grid,newnumber)
  12.         m = len(grid)
  13.         n = len(grid[0])
  14.         newnumber = 1
  15.         area = {}
  16.         maxarea = 0
  17.         for i in range(m):
  18.             for j in range(n):
  19.                 if grid[i][j] == 1:
  20.                     newnumber+=1
  21.                     area[newnumber] = dfs(i,j,grid,newnumber)
  22.                     maxarea = max(maxarea,area[newnumber])
  23.         maxareares = 0
  25.         for i in range(m):
  26.             for j in range(n):
  27.                 if grid[i][j] == 0:
  28.                     areares = 1
  29.                     res = []
  30.                     if i+1<m :
  31.                         res.append(grid[i+1][j])
  32.                     if i-1>=0:
  33.                         res.append(grid[i-1][j])
  34.                     if j+1<n:
  35.                         res.append(grid[i][j+1])
  36.                     if j-1>=0:
  37.                         res.append(grid[i][j-1])
  38.                     res = list(set(res))
  39.                     for k in range(len(res)):
  40.                         areares += area.get(res[k],0) 
  41.                     maxareares = max(maxareares,areares)
  42.         return max(maxareares,maxarea)

√778.水位上升的泳池中游泳

相同类型：1631. 最小体力消耗路径
image.png
image.png

保存所有结果，选最小值。

  1. class Solution:
  2.     def swimInWater(self, grid: List[List[int]]) -> int:
  3.         dir=[1,0,-1,0,0,1,0,-1]
  4.         max_grid =  max(max(row) for row in grid)
  5.         ans=max_grid+1   # 这个不知道为什么参数不能传递
  6.         res=[]
  7.         def dfs(x,y,val,ans):
  8.             if val>=ans:   # 在这里剪枝
  9.                 return
  10.             for i in range(4):
  11.                 nx = x+dir[2*i]
  12.                 ny = y+dir[2*i+1]
  13.                 if nx>=0 and nx<n and ny>=0 and ny<n:
  14.                     nowVal = max(grid[nx][ny],val)
  15.                     if times[nx][ny]>nowVal and nowVal<ans:
  16.                         times[nx][ny]=nowVal
  17.                         if nx==ny and nx==n-1:
  18.                             ans = nowVal
  19.                             res.append(ans)
  20.                             return
  21.                         dfs(nx,ny,nowVal,ans)
  22.         n = len(grid)
  23.         times = [[max_grid+1]*n for _ in range (n)]
  24.         times[0][0]=grid[0][0]
  25.         dfs(0,0,times[0][0],ans)
  26.         return min(res)

二分法加DFS

  1. class Solution:
  2.     def swimInWater(self, grid: List[List[int]]) -> int:
  3.         n = len(grid)
  4.         def dfs(t, x, y, visited):
  5.             if x == y == n - 1:
  6.                 return True
  7.             visited[x][y] = True
  8.             for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
  9.                 nx, ny = x + dx, y + dy
  10.                 if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] <= t:     
  11.                     if dfs(t, nx, ny, visited):
  12.                         return True
  13.             return False
  15.         left = max(grid[0][0], grid[-1][-1])
  16.         right = n * n - 1   # 注意题意，数组是排列，最大值就是N*N-1
  17.         while left <= right:   # 闭区间[left,right]
  18.             mid = (left + right) // 2
  19.             visited = [[False] * n for _ in range(n)]
  20.             if dfs(mid, 0, 0, visited):   # 如果这个值可以到边界，可以缩小区域
  21.                 right = mid - 1
  22.             else:
  23.                 left = mid + 1
  24.         return left   # 这里为什么返回left

image.png

BFS不是很懂

  1. class Solution:
  2.     def swimInWater(self, grid: List[List[int]]) -> int:
  3.         res = 0
  4.         n = len(grid)
  5.         heap = [(grid[0][0],0,0)]
  6.         visited = set([(0,0)])
  8.         while heap:
  9.             height,x,y = heapq.heappop(heap)
  10.             res = max(res,height)
  11.             if x == n-1 and y == n-1:
  12.                 return res
  14.             for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
  15.                 new_x,new_y = x + dx,y + dy
  16.                 if 0 <= new_x < n and 0 <= new_y < n and (new_x,new_y) not in visited:
  17.                     visited.add((new_x,new_y))
  18.                     heapq.heappush(heap,(grid[new_x][new_y],new_x,new_y))
  20.         return -1

√417.太平洋大西洋水流问题

image.png
image.png
个人版答案，从边界遍历，分别从太平洋和大西洋边界位置出发遍历，同时被它们两遍历到的，就是答案
遍历方法，就是按高度，找下一个大于等于此时遍历的点

  1. class Solution:
  2.     def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
  3.         def dfs(x,y,point):
  4.             point.append((x,y))   #注意，这里必须是（），不能是[],集合求交集，必须是hashtable格式
  5.             direction = [[-1,0],[1,0],[0,1],[0,-1]]
  6.             for d in direction:
  7.                 nx=x+d[0]
  8.                 ny=y+d[1]
  9.                 if nx>=0 and ny>=0 and nx<len(heights) and ny<len(heights[0]) and heights[nx][ny]>=heights[x][y] and (nx,ny) not in point:
  10.                     dfs(nx,ny,point)
  11.         point=[]
  12.         for i in range (len(heights[0])):   # 第一行
  13.             dfs(0,i,point)
  14.         for i in range (len(heights)):     # 第一列
  15.             dfs(i,0,point)
  16.         print(point)
  17.         point2=[]
  18.         for i in range (len(heights[0])):     # 最后一行
  19.             dfs(len(heights)-1,i,point2)
  20.         for i in range (len(heights)):        # 最后一列
  21.             dfs(i,len(heights[0])-1,point2)
  22.         print(point2)
  23.         print(set(point2) & set(point))
  24.         return list(set(point2) & set(point))

大佬版，思路一样

  1. class Solution:
  2.     def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
  3.         if not matrix or not matrix[0]: return []
  4.         # 流向太平洋的位置
  5.         res1 = set()
  6.         # 流向大西洋的位置
  7.         res2 = set()
  8.         row = len(matrix)
  9.         col = len(matrix[0])
  11.         # 从边界遍历
  12.         def dfs(i, j, cur, res):
  13.             res.add((i, j))
  14.             for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
  15.                 tmp_i = i + x
  16.                 tmp_j = j + y
  17.                 if 0 <= tmp_i < row and 0 <= tmp_j < col and matrix[i][j] <= matrix[tmp_i][tmp_j] and (tmp_i, tmp_j) not in res: 
  18.                     dfs(tmp_i, tmp_j, matrix[i][j], res)
  19.         # 太平洋
  20.         for i in range(row):
  21.             dfs(i, 0, 0, res1)
  22.         # 太平洋
  23.         for j in range(col):
  24.             dfs(0, j, 0, res1)
  25.         # 大西洋
  26.         for i in range(row):
  27.             dfs(i, col - 1, 0, res2)
  28.         # 大西洋
  29.         for j in range(col):
  30.             dfs(row - 1, j, 0, res2)
  32.         return list(res1 & res2)

速度慢的原因可能是集合判断那里，个人版答案不知道为什么有重复结果。
image.png

√934.最短的桥

image.png

×749.隔离病毒

image.png
image.png