题目链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
难度：中等

描述：
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

题解

  1. class Solution:
  2.     def exist(self, board: List[List[str]], word: str) -> bool:
  3.         m, n = len(board), len(board[0])
  5.         def dfs(i, j, k):
  6.             if k == len(word):
  7.                 return True
  9.             if i < 0 or i >= m:
  10.                 return False
  12.             if j < 0 or j >= n:
  13.                 return False
  15.             if board[i][j] != word[k]:
  16.                 return False
  18.             board[i][j] = ""
  19.             ret = dfs(i-1, j, k+1) or dfs(i+1, j, k+1) or dfs(i, j-1, k+1) or dfs(i, j+1, k+1)
  20.             board[i][j] = word[k]
  21.             return ret
  23.         for i in range(m):
  24.             for j in range(n):
  25.                 if dfs(i, j, 0):
  26.                     return True
  28.         return False