剑指offer12

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

示例一

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true

示例二

输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false

• 矩阵搜索dfs+回溯。dfs()写法：先判定最底层边界值，再判定非法越界情况，最后写dfs递归方向。

• 回溯法精髓：

if(dfs(index+1))
       return true; //底层搜索到结果传结果true或者false回上层，影响上层
else
	visit[i][j]=0; //当前结点失败，访问位置为0，返回false给上层
	return false;

• 不开辟访问数组，可以在原数组上面修改来标记是否访问过，访问过则置为0，失败则回溯还原为原本的字符。