深度优先搜索|79, 695,212

单词搜索

用的是深度优先搜索，这种判断类型的回溯我就一直不知道要怎么回退，然后勉强写了一个。
这里还有一个注意事项就是，走到最后一个元素的时候，我设置的direction list里头就只有用过的几个元素，再加上我写的if used这个时候他就走不下去了，也不会到下一层的index+1了，这个时候又可以观察到，如果走到最后有一个元素了和word也对得上其实并不需要再去看有没有direction了，直接去index+1不用管i，j是谁就能直接True，所以这个地方可以加一个判断就是如果走到这里已经在word最后一个字母后面了，直接True。
然后写到这里就会发现，如果直接出去了，那么

if index == len(word):return True 

这句好像根本不需要，后来发现确实不需要。

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def direction(i,j,m,n):l = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]if i == 0:l.remove([i-1,j])if j == 0:l.remove([i,j-1])if i == m-1:l.remove([i+1,j])if j == n-1:l.remove([i,j+1])return l def backtracking(index,i,j):#if index == len(word):#return True l = direction(i,j,m,n)if board[i][j] != word[index]: return Falseused[i][j] = Truefor k1,k2 in l:if index == len(word) - 1:return True if used[k1][k2]: continueif backtracking(index+1,k1,k2):return Trueif l == [] and index == len(word)-1:return Trueused[i][j] = Falsereturn Falsem = len(board)n = len(board[0])used = [[False]*n for _ in range(m)]for i in range(m):for j in range(n):if backtracking(0,i,j):return True return False

岛屿的最大面积

这个题没上面的难，因为他知道是1都是连着的，所以不用回退。

class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:def direction(i,j,m,n):l = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]if i == 0:l.remove([i-1,j])if j == 0:l.remove([i,j-1])if i == m-1:l.remove([i+1,j])if j == n-1:l.remove([i,j+1])return l m = len(grid)n = len(grid[0])used = [[False]*n for _ in range(m)]def backtracking(i,j):nonlocal resif grid[i][j] == 0: return 0l = direction(i,j,m,n)res += 1used[i][j] = Truefor k1,k2 in l:if used[k1][k2]:continuebacktracking(k1,k2)return island = 0for i in range(m):for j in range(n):res = 0backtracking(i,j)island = max(island,res)return island

单词搜索II

在上一题的基础上加了一层循环，然后剪枝了一下，大多数还是能运行，就是太长了就超时了
42 / 65，这里有个要点是，每次单词的used list都要重新设，不然路都堵死了。

class Solution:def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:def direction(i,j,m,n):l = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]if i == 0:l.remove([i-1,j])if j == 0:l.remove([i,j-1])if i == m-1:l.remove([i+1,j])if j == n-1:l.remove([i,j+1])return l def backtracking(index,word,i,j):l = direction(i,j,m,n)if board[i][j] != word[index]: return Falseused[i][j] = Truefor k1,k2 in l:if index == len(word) - 1:return True if used[k1][k2]: continueif backtracking(index+1,word,k1,k2):return Trueif l == [] and index == len(word)-1:return Trueused[i][j] = Falsereturn Falsem = len(board)n = len(board[0])res = []for k in words:used = [[False]*n for _ in range(m)]for i in range(m):if k in res:breakfor j in range(n):#print(i,j,k,res)if k in res:breakif backtracking(0,k,i,j):res.append(k)