题目：
给定一个m*n的二维字符网格board和一个字符串单词word,如果word存在于网格中，返回True,否则返回False
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或者垂直相邻的单元格，同一个单元格的字母不允许被重复使用
方法一：回溯
设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数 check(i,j,k) 的执行步骤如下：
如果 board[i][j]=word[k]，当前字符不匹配，直接返回 false
如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true
否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false。
对每一个位置 (i,j) 都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
directions=[(0,1),(0,-1),(1,0),(-1,0)] #定义四个方向（右，左，下，上）的移动方式
def check(i,j,k): #函数用于回溯搜索
if board[i][j]!=word[k]: #当前位置字符不匹配word[k],直接返回False
return False
if k==len(word)-1: #如果匹配到了Word的最后一个字符，则返回True,表示找到完整单词
return True
#如果 board[i][j] 位置匹配 word[k]，则继续搜索。
visited.add((i,j)) #记录当前位置已访问，防止重复访问
result=False
for di,dj in directions: #判断临界方向的字符
newi,newj=i+di,j+dj
if 0<=newi<len(board) and 0<=newj<len(board[0]):# # 确保新的位置在 board 内
if (newi,newj)not in visited: #判断新位置是否被访问过
if check(newi,newj,k+1): #递归检查下一个位置
result=True
break
visited.remove((i,j))#回溯时，移除当前位置 (i, j)，恢复未访问状态
return result
h,w=len(board),len(board[0])
visited=set()
for i in range(h):
for j in range(w): #从每个位置 (i, j) 开始搜索
if check(i,j,0):
return True #只要找到一个匹配的单词，就返回 True
return False
时间复杂度：O(MN⋅3**L)，其中 M,N 为网格的长度与宽度，L 为字符串 word 的长度。
空间复杂度：O(MN)。额外开辟了 O(MN) 的 visited 数组
源自力扣官方题解