题解 | #矩阵中的路径#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int tmp[20][20];

    bool dfs(vector<vector<char>>& src,int x, int y, string word, int index){
        if(index >= word.length())return true;
        
        if(src[x][y] != word[index])return false;
        tmp[x][y] = 1;
        index += 1;

        if(word[index] == '\0')return true;

        bool res = false;

        //同时还要控制不要走回头路
        //往上
        if(x != 0 && tmp[x - 1][y] == 0){
            if(dfs(src,x - 1,y,word,index))return true;
        }
        //往下
        if(x != src.size() - 1 && tmp[x + 1][y] == 0){
            if(dfs(src,x + 1,y,word,index))return true;
        }
        //往左
        if(y != 0 && tmp[x][y - 1] == 0){
            if(dfs(src,x,y - 1,word,index))return true;
        }
        //往右
        if(y != src[0].size() - 1 && tmp[x][y + 1] == 0){
            if(dfs(src,x,y + 1,word,index))return true;
        }

        //进行回溯
        tmp[x][y] = 0;
        return res;
    }

    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if(word.size() == 0)return true;

        memset(tmp,0,400);

        //1.遍历每个入口，查找起点
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(dfs(matrix,i,j,word,0)){
                    return true;
                }
            }
        }

        return false;
    }
};

该题使用暴力回溯进行搜索路径。首先，先遍历每个元素来确定起始位置，也就是入口，通过入口的坐标进行回溯，如果从这个入口进行回溯找到了对于的路径，那么则返回true；如果遍历完所有元素，都还没找到，说明没有路径符合，返回false。回溯的具体过程是，进入回溯的时候，首先先判断当前从二维数组中遍历到的元素是否符合target字符数组中所遍历到位置的元素，如果不相等，则返回false。如果相等，则判断是否遍历完target字符数组，如果遍历完，则说明找到了，则返回true。如果没遍历完，则用一个临时二维数组去保存当前位置，将当前位置置为1，来控制遍历的时候不能遍历以前已经遍历到的位置。然后进行上下左右进行回溯，在要回溯前判断当前所处位置是否能上下左右移动，还要判断下一个要遍历的位置是否被遍历过，如果从当前位置进行回溯后接收到true，说明找到了路径，返回true。如果上下左右都遍历完还找不到，则说明当前入口不对，返回false。

时间复杂度是O(n * m * 4 ^k)，空间复杂度是O(m*n)。