给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在
board更大的情况下可以更快解决问题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（未完成）解1 2021/9/11 O(?)
from collections import defaultdict
def help_sizhou(a:list, b:list)->bool:
# 判断b是不是在a的四周
ax=a[0];ay=a[1]
bx=b[0];by=b[1]
if (bx==ax and by==ay+1): return True
if (bx==ax and by==ay-1): return True
if (by==ay and bx==ax+1): return True
if (by==ay and bx==ax+1): return True
return False
def exist(board: list, word: str) -> bool:
# 上下左右4个方向，
# 起点，就是board中所有位置的word[0]
# 题目限定了m,n∈[1,6]，word.len∈[1,15]
# 由于规模很小，最大也就6x6的格子，word最长也才15个字符，完全可以用dict把word中所有字母在board中的
# 位置存下来，只不过用过的不能用了要注意
# dict，存[[x,y],used]，坐标，和是否已经使用，
# 每次用完，记得还原used为0
d=defaultdict(list)
m=board.__len__()
n=board[0].__len__()
for x in range(0,m):
for y in range(0,n):
c=board[x][y]
if c in word:
d[c].append([[x,y],0])
be=word[0]
if d.get(be)==None: return False
for x in d[be]:
rest=word[1:]
i=x[0][0];j=x[0][1]
for c in rest:
# [TODO] 好像这么做并非一个好的选择，还是需要递归，可能还不如顺序的遍历来的简单
if __name__ == ‘__main__‘:
# true
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word = "ABCCED"
print(exist(board,word))
# true
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word = "SEE"
# false
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word = "ABCB"