DFS

题解1：

#include<iostream>
using namespace std;
#include<vector>
bool dfs(vector<vector<char>> matrix, int i, int row, int col, string str) {
	//先找到入口
	if (matrix[row][col] != str[i]) return false;//没找到入口，返回
	//cout << "找到第" << i << "个元素:" << matrix[row][col] << endl;
	//cout << "元素位置：" << row << " " << col << endl;
	matrix[row][col] = '*';//把每次成功找到的走过的路径上的字符设置为*；防止str中存在重复的元素
	i++;//每一次找到了之后，i=i+1
	//找到对应的值之后，找出口
	if (i == str.size()) return true; //当找到的路径数目等于字符长度，那么说明路径已经找到了

	//设置偏移量，要么向上要么向下要么向左要么向右
	int dx[4][2] = { {0,-1},{0,1},
					 {-1,0},{1,0}
	};//分别是向左 向右 向上 向下
	for (int j = 0; j < 4; j++) //每次可以有四个方向进行移动
	{
		row = row + dx[j][0];
		col = col + dx[j][1];
		if (row >= 0 && row < matrix.size() && col >= 0 && col < matrix[0].size())
		{
			if (dfs(matrix, i, row, col, str))  //找到了
				return true;		
		}
		row = row - dx[j][0];//当超出边界，返回现场；当移动之后没找到，返回现场
		col = col - dx[j][1];
	}
	//如果没找到
	return false;
}

bool hasPath(vector<vector<char> >& matrix, string word) {
	// write code here
	int rowLen = matrix.size();//行数
	int colLen = matrix[0].size();//列数
	for (int i = 0; i < rowLen; i++)
	{
		for (int j = 0; j < colLen; j++)
		{
			//cout << "(" << i << "," << j << ")" << endl;
			if (dfs(matrix, 0, i, j, word))
				return true;	
		}
	}
	//回溯法第一个步骤是要找到矩阵的入口单元格，所以在本例中，需要通过循环找到入口的单元格
    //而像机器人的运动范围一例，题目中已经给出了入口的单元格，因此可以直接进行递归调用(在采用DFS)。
	return false;
}


int main() {
	vector<vector<char>> matrix;
	//= { { 'a','b','c','d' },
	//						       { 'e','f','g','h' } ,
	//						       { 'i','j','k','l' } ,
	//						       { 'm','n','o','p'}};
	vector<char> v1 = { 'a','b','c','e','h','j','i','g' };
	vector<char> v2 = { 's','f','c','s','l','o','p','q' };
	vector<char> v3 = { 'a','d','e','e' ,'m','n','o','e' };
	vector<char> v4 = { 'a','d','i','d','e','j','f','m' };
	vector<char> v5 = { 'v','c','e','i','f','g','g','s' };
	matrix.push_back(v1);
	matrix.push_back(v2);
	matrix.push_back(v3);
	matrix.push_back(v4);
	matrix.push_back(v5);

	string str = "sggfiecvaasa";
	cout << "是否存在路径sggfiecvaasa：" << hasPath(matrix, str) << endl;

	system("pause");
	return 0;
}

题解2：

void dfs(vector<vector<char>> matrix, int& count, int row, int col, string str, vector<vector<bool>>& visited) {
	cout <<"坐标变化" << "(" << row << " " << col << "）"<<"找"<<str[count] <<"于"<<count << endl;
	if (row < 0 || row > matrix.size() - 1 || col < 0 || col > matrix[0].size() - 1)
		return; //出口条件：超出边界，返回
	if (matrix[row][col] != str[count])
		return; //出口条件：移动的单元格不是对应的字符，返回
	cout << visited[row][col] << endl;
	if (visited[row][col] == 1)
		return; //出口条件：最终当对应位置全部被走过后，返回

	cout << "找到第" << count << "个--------:" << matrix[row][col];
	cout << "(" << row << " " << col << "）"<<endl;
	//找到对应的字符后
	visited[row][col] = 1;//把每次成功找到的走过的路径上的字符设置为真
	count++;//每一次找到了之后，count=count+1
	if (count == str.size()) return; //所有字符找到，返回

	//开始向四个方向递归
	dfs(matrix, count, row - 1, col, str, visited);
	dfs(matrix, count, row + 1, col, str, visited);
	dfs(matrix, count, row, col - 1, str, visited);
	dfs(matrix, count, row, col + 1, str, visited);
	//如果不采用循环方式进行四个方向的递归，那么就必须在四个方向递归完毕之和，
	//还没有找到对应的字符，说明有重复元素，就需要进行回退，count--；
	//如果全部找到了，返回,count不能再改变，需要作为getIn的判断条件。
	if (count == str.size())
		return;
	else {
		count--;//当四个方向都不是对应字符，说明上一个字符位置不对
		visited[row][col] = 0;//返回时候，count和visited都要更改
	}
}
//找入口位置，即是字符串的第一个元素在矩阵中的位置
bool getIn(vector<vector<char>> matrix,int row, int col, string str) {
	if (matrix[row][col] != str[0]) return false;//没有找到入口，即是第一个字符
	//找到入口，开始递归
	int count = 0;//注意，即使找到了第一个字符，count只能为0，count在递归中自增
	//定义一个bool型二维数组，同时进行初始化，用来存放已经被访问过的单元格
	vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), 0));
	dfs(matrix, count, row, col, str, visited);

	if (count == str.size())//当找到的个数和字符串相同时，返回true，否在返回false;
		return true;
	return false;
}
bool hasPath(vector<vector<char>> matrix, string word) {
	// write code here
	int rowLen = matrix.size();//行数
	int colLen = matrix[0].size();//列数
	//找第一个字符所在位置,如果第一个位置找到了，但是不对，重新查找
	for (int i = 0; i < rowLen; i++)
	{
		for (int j = 0; j < colLen; j++)
		{
			if (getIn(matrix, i, j, word))
				return true;
		}
	}
	return false;
}