题意：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1：
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false
实现思想:先用迭代找到 字符串的第一个元素，从此位置开始向上下左右四个位置开始递归回溯，并且，要记录已经使用的位置。
class Solution
{
int _row;
int _column;
int _len;
vector<vector<bool>> _status;// 记录矩阵中的元素是否使用
public:
bool exist(vector<vector<char>> &board, string word)
{
_row = board.size();
_len = word.size();
if (_len == 0)
return true;
if (_row < 1)
{
return false;
}
_column = board[0].size();
if (0 == _column)
{
return false;
}
for (int i = 0; i < _row; i++)
{
for (int j = 0; j < _column; j++)
{
if (board[i][j] == word[0])
{
_status = vector<vector<bool>>(_row, vector<bool>(_column, false));
if(search(board,word,i,j,0)){
return true;
}
}
}
}
return false;
}
bool search(const vector<vector<char>> &board, const string &word, int x, int y, int curlen)
{
if (x < 0 || x >= _row)
return false;
if (y < 0 || y >= _column)
return false;
if (_status[x][y])
return false;
if(curlen>=_len)
return false;
if (board[x][y] != word[curlen])// 不相等
return false;
if(curlen==(_len-1)) //相等且为最后一个
return true;
_status[x][y] = true;
bool ret= (search(board,word,x+1,y,curlen+1)||\
search(board,word,x-1,y,curlen+1)||\
search(board,word,x,y-1,curlen+1)||\
search(board,word,x,y+1,curlen+1));
if(!ret)
_status[x][y]=false;//此路不通，归还使用
return ret;
}
};
