79. Word Search

题意：

在一个二维数组中是否可以匹配到一个字符串，这个字符串在二维数组中可以拐弯，但必须连续。

思路：深搜+回溯

遍历数组，若数组中元素等于字符串第一个字符进入深搜。
深搜中有一个参数k，表示已经匹配的字符数，若k==word.size()，则表示字符串完全匹配成功。
有一个二维数组参数flag，flag[i][j]表示i j位置是否已经被划入匹配范围，若flag[i][j]=0，则表示已匹配，后面不能再使用这个字符。
在每次dfs开始时需将对应位置置0，然后在结束时需要将对应位置置1.

bool dfs(vector<vector<char>>& board, string &word, vector<vector<bool>> &flag, int i, int j, int k) {//91%
	//cout << k << " " << i << " " << j << endl;
	if (k == word.size())
		return true;
	flag[i][j] = 0;
	if (i > 0 && flag[i - 1][j] && board[i - 1][j] == word[k] && dfs(board, word, flag, i - 1, j, k + 1))
		return true;
	if (j > 0 && flag[i][j - 1] && board[i][j - 1] == word[k] && dfs(board, word, flag, i, j - 1, k + 1))
		return true;
	if (i < board.size() - 1 && flag[i + 1][j] && board[i + 1][j] == word[k] && dfs(board, word, flag, i + 1, j, k + 1))
		return true;
	if (j < board[0].size() - 1 && flag[i][j + 1] && board[i][j + 1] == word[k] && dfs(board, word, flag, i, j + 1, k + 1))
		return true;
	flag[i][j] = 1;
	return false;
}

bool exist(vector<vector<char>>& board, string word) {
	int m = board.size(), n = board[0].size(), sz = word.size();
	vector<vector<bool>> flag(m, vector<bool>(n, 1));
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
			if (board[i][j] == word[0] && dfs(board, word,flag, i, j, 1))
				return true;
	return false;
}