给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
image.png
- DFS (deep first search)
- 剪枝：遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为「可行性剪枝」 。
- 递归参数：当前的matrix的索引 i,j； 当前想要匹配的字符索引 k
- 终止条件：F ：1. 没匹配上 2. 越界 3. 当前已访问过； T： k = len(word) - 1，即word的每一个字符都匹配完了
- 标记当前矩阵元素： 将 board[i][j] 修改为 -1 ，代表此元素visited，防止之后搜索时重复访问。
- 递归：上下左右四个方向去找
*注意：先确认边界；如果一条路没走通，记得还原；
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def search(i,j,k):
# 矩阵[i][j]和word[k]匹配
# 先确认边界
if 0<= i < len(board) and 0<= j < len(board[0]):
if word[k] != board[i][j]:
return False
else:
# 如果当前元素是word的最后一个字母，直接返回true
if k == len(word)-1:
return True
# 递归，并且当前状态改为visitied
board[i][j] = '' # visited
result = search(i-1,j,k+1) or search(i+1,j,k+1) or search(i,j-1,k+1) or search(i,j+1,k+1) # 上、下、左、右
# 如果没找到，需要继续找，记得把当前的这个字母还原
if result == False:
board[i][j] = word[k]
return result
else:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if search(i,j,0):
return True
return False
```
