79. Word search [DFS + backtracking visit + traversal starting point]

analysis

use dfs + visit + The idea of backtracking
Then find the right entrance
Take a look at the next position up and down, left and right. It's suitable to take one （ Here we use visit to flash back ）
dfs Traverse all possible positions , As long as there is a penny dfs return True
So the whole thing is True Of , If there is no return True
unfortunately , That can only be False
Finally, if you can go to the last position, you can return

ac code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])     
        k = len(word)


        # dfs +  to flash back 
        def dfs(r, c, idx):
            

            if idx == k - 1:
                return True
            
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and word[idx + 1] == board[nr][nc] and visit[nr][nc] is False:
                    visit[nr][nc] = True
                    temp = dfs(nr, nc, idx + 1)
                    if temp: return True
                    visit[nr][nc] = False
            
            return False
        
        #  Traverse each starting point 
        for i in range(m):
            for j in range(n):
                visit = [[False] * n for _ in range(m)]
                if board[i][j] == word[0]:
                    visit[i][j] = True
                    if dfs(i, j, 0):  return True
        
        return False

summary

dfs The parameters of record the current position and the current position of the last element that has been placed idx
The success condition is to reach the last index