LC 79单词搜索Word Search　中等

在二维字符网格中判断单词 word 是否能由相邻（四方向）单元格字母按顺序组成，同一格不可重复使用。

思路 回溯：从每个匹配 word[0] 的格子出发四方向匹配，visited 标记防重走，失败撤销；O(mn·3^L)。

class Solution:
    def exist(self, board: List[List[str]],
              word: str) -> bool:
        m, n = len(board), len(board[0])
        vis = [[False] * n for _ in range(m)]

        def dfs(i, j, k):
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            vis[i][j] = True
            for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
                x, y = i + dx, j + dy
                if (0 <= x < m and 0 <= y < n
                        and not vis[x][y]
                        and dfs(x, y, k + 1)):
                    return True
            vis[i][j] = False
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False