作者：翟天保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
解题思路：
本题是回溯法的经典题目，也常用于解决迷宫问题。思路如下：
- 用flag记录当前点是否走过，结合矩阵数据和字符数据，运用dfs（深度优先遍历）进行路径探索。
- dfs中，若当前点出现下标越界、字符不匹配和已经走过的情况，则终止当前路；若字符匹配上了，则认为当前点满足要求，先暂时将flag设为true，并以该点为中心，继续向上下左右四个方向探索新的点位；若四个方向有路可走，则依次递进，直到有一条路径和字符串完全对应；若四个方向均无路，则回退一步，并将当前点的flag设为false。
总的来说，题目运用了回溯、深度优先遍历和递归的思想。文章来源：https://www.toymoban.com/news/detail-514654.html
测试代码：
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;
}
};六一儿童节快乐！文章来源地址https://www.toymoban.com/news/detail-514654.html
到了这里，关于剑指offer(C++)-JZ12：矩阵中的路径(算法-回溯)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
