【原】剑指offer(C++)-JZ12：矩阵中的路径(算法-回溯)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如A矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

数据范围：0≤n,m≤20 ,1≤len≤25 

示例：

输入：

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"

返回值：

true

解题思路：

本题是回溯法的经典题目，也常用于解决迷宫问题。思路如下：

1. 用flag记录当前点是否走过，结合矩阵数据和字符数据，运用dfs（深度优先遍历）进行路径探索。
2. dfs中，若当前点出现下标越界、字符不匹配和已经走过的情况，则终止当前路；若字符匹配上了，则认为当前点满足要求，先暂时将flag设为true，并以该点为中心，继续向上下左右四个方向探索新的点位；若四个方向有路可走，则依次递进，直到有一条路径和字符串完全对应；若四个方向均无路，则回退一步，并将当前点的flag设为false。

总的来说，题目运用了回溯、深度优先遍历和递归的思想。

测试代码：

class Solution {
public:
    // 深度优先遍历
    bool dfs(vector<vector<char>>& matrix, int m, int n, int i, int j, string word, int k, vector<vector<bool>>& flag){
        // 下标越界、字符不匹配、已经遍历过，则false
        if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] != word[k] || flag[i][j])
            return false;
        // 刷新标识符
        flag[i][j]= true;
        // 字符串全部集齐，则true
        if(k == int(word.size() - 1))
            return true;
        // 上下左右四方向搜索，若有路通，则true    
        if(dfs(matrix, m, n, i - 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i + 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i, j - 1, word, k + 1, flag)
           || dfs(matrix, m, n, i, j +1 , word, k + 1, flag))
           return true;
        // 该点位无有效路径，倒退一步，此点未使用，所以重置flag
        flag[i][j] = false;
        return false;
    }

    // 是否有目标路径
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // 空数据判断
        int m = int(matrix.size());
        int n = int(matrix[0].size());
        if(m == 0 || n == 0)
            return false;
        // flag二维容器存放标识符，判断当前点是否走过
        vector<vector<bool>> flag(m,vector<bool>(n, false));
        // 遍历
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(dfs(matrix, m, n, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
};

六一儿童节快乐！