题解 | #矩阵中的路径#

回溯法需要考虑很多条件，如下：

1、超过边界，需要返回到原来的索引位置

2、没超过边界，但是没有找到值，需要返回到原来的索引位置

3、没超过边界，找到值

3.1 找到值之和，需要把找到的值设置为*，防止word中存在重复的元素，当循环查找时候，若存在重复元素，而没有将之前走过的路径设置为*，就会存在被认为找到，这就存在重复找到。所以必须将走过的路径的元素设置为*。

3.2 bool dfs(vector matrix, int i, int row, int col, string str)中，matrix不能加引用，因为该例子没有恢复原字符的代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool dfs(vector<vector<char>> matrix, int i, int row, int col, string str) {
        //先找到入口
        if (matrix[row][col] != str[i]) return false;//没找到入口，返回
        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++)
		{
			if (dfs(matrix, 0, i, j, word))
				return true;
		}
	}
	return false;
    }
};