题解 | #矩阵中的路径#

class Solution {
public:
	/**
	 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	 *
	 *
	 * @param matrix char字符型vector<vector<>>
	 * @param word string字符串
	 * @return bool布尔型
	 */
	bool hasPath(vector<vector<char> >& matrix, string word) {
		// write code here
		m_s = word; len = word.size();
		m_v = matrix;
		line = matrix.size(); column = matrix[0].size();
		for (int i = 0; i < line; i++) {
			visited.emplace_back(vector<bool>());
			for (int j = 0; j < column; j++)
				visited[i].emplace_back(false);
		}
		for (int i = 0; i < line; i++)
			for (int j = 0; j < column; j++) {
				visited[i][j] = true;
				if (m_v[i][j] == m_s[0] && dfs(i, j, 0)) {
					return true;//找到一条路径即可
				}
				visited[i][j] = false;
			}
				
		return false;
		
	}
private:
	string m_s;
	int len;
	vector<vector<char> > m_v;
	vector<vector<bool>>visited;
	int line, column;
	//matrix[x][y]已经确认完毕，找下一步，进行到第k个字符
	bool dfs(int x,int y,int k) {
		if (k == len-1)return true;//说明0~len-1个字符全部匹配完毕
		bool res1, res2, res3, res4;
		res1 = res2 = res3 = res4 = false;
		//上下左右
		if (x > 0 && !visited[x - 1][y] && m_v[x - 1][y] == m_s[k + 1]) {
			visited[x - 1][y] = true;
			res1 = dfs(x - 1, y, k + 1);
			visited[x - 1][y] = false;
		}
		if (x < line-1 && !visited[x + 1][y] && m_v[x + 1][y] == m_s[k + 1]) {
			visited[x + 1][y] = true;
			res2 = dfs(x + 1, y, k + 1);
			visited[x + 1][y] = false;
		}
		if (y > 0 && !visited[x][y - 1] && m_v[x][y - 1] == m_s[k + 1]) {
			visited[x][y - 1] = true;
			res3 = dfs(x, y - 1, k + 1);
			visited[x][y - 1] = false;
		}
		if (y < column - 1 && !visited[x][y + 1] && m_v[x][y + 1] == m_s[k + 1]) {
			visited[x][y + 1] = true;
			res4 = dfs(x, y + 1, k + 1);
			visited[x][y + 1] = false;
		}
		return res1 || res2 || res3 || res4;
	}
};