顺序是关键

1、枚举起点
2、从起点开始，依次搜索下一个点的位置
3、在枚举的过程中，要保证和目标单词匹配

时间复杂度o(n^2.3^k)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not len(board) or not len(board[0]): return False
        n = len(board); m = len(board[0])

        # 枚举起点，从(0,0)开始
        i = 0
        while i < n:
            j = 0
            while j < m:
                if (self.dfs(board, i, j, word, 0)):
                    return True
                j += 1
            i += 1
        return False

    def dfs(self, board, x, y, word, u): 
    # u代表word当前的索引; x,y表示当前元素的二维索引
        if board[x][y] != word[u]: return False
        if u == len(word) - 1: return True

        board[x][y] = '.' # 当前格子已经被用过，要进行标记
        self.dx = [-1, 0, 1 ,0]; self.dy = [0, 1, 0, -1] # 上右下左四个方向移动导致坐标的变化
        for i in range(4):
            a = x + self.dx[i]; b = y + self.dy[i]
            n = len(board); m = len(board[0])  
            if a >= 0 and a < n and b >= 0 and b < m: # 保证不越界
                if (self.dfs(board, a, b, word, u + 1)): 
                    return True

        board[x][y] = word[u] # 回溯，恢复现场
        return False