【C/C++练习题】回溯法判断矩阵中的路径
【摘要】
《剑指Offer》面试题12：矩阵中的路径
题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母...
《剑指Offer》面试题12：矩阵中的路径
题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
-
A B T G
-
C F C S
-
J D E H
算法分析
对于这种一个问题有多个步骤，一个步骤又对应多个选项的问题，使用回溯法进行分析。基本思想是，首先对可选项（所有可能满足条件的选项）进行遍历，如果可选项满足规定的条件，将可选项作为下一个步骤；如果可选项中没有符合条件的结果，则返回上一个步骤，对其他可选项进行分析。直到最后一个步骤确定了，取得最终的结果。
另外，还要有一个数组，用来标记哪个步骤已经被执行过了，避免重复执行这个步骤。
问题分析
对于上述问题分析，"BFCE"是目标路径
- 所有选项都是可选项，通过遍历分析只有'B'符合条件
- 在‘B’的周围，'A' 'F' 'T'都是可选项，通过判断只有'B'下面的'F'符合条件
- 在'F'的周围，'B' 'C' 'D' 'C'都是可选项，通过判断有'F'左边的'C'和右边的'C'符合条件
- 在左'C'周围,'A' 'G'是可选项，但都不符合条件，退回上一个步骤'F'（分析其他可选项）；
- 在右'C'周围，'T' 'F' 'E' 'S'都是可选项，'E'符合条件
上述是回溯法的分析过程
代码实现
由于回溯法的递归特性，这里使用递归的方法实现回溯分析
-
#include "iostream"
-
#include <cstring>
-
#include <stack>
-
-
using namespace std;
-
-
-
bool hasPath(const char* matrix, int rows, int cols, const char* str);
-
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited);
-
-
//回溯法进行矩阵中的路径判断
-
//输入：源数组 matrix， 行数 rows， 列数 cols，目标字符串 str
-
//输出：有目标路径 true, 无解 false
-
bool hasPath(const char* matrix, int rows, int cols, const char* str)
-
{
-
-
-
//1.判断参数有效性
-
if(matrix == nullptr || rows < 1 || cols < 1 || str == nullptr)
-
return false;
-
-
//2.设置标记路径的数组
-
bool *visited = new bool[rows * cols];
-
memset(visited, 0, rows * cols);
-
-
int pathLength = 0;
-
for(int row = 0; row < rows; ++row)
-
{//3.遍历所有可选项，从可选项中选出符合条件的位置，进行回溯
-
for(int col = 0; col < cols; ++col)
-
{
-
if(hasPathCore(matrix, rows, cols, row, col, str,
-
pathLength, visited))
-
{
-
return true;
-
}
-
}
-
}
-
-
//4.清理堆空间
-
delete[] visited;
-
-
return false;
-
}
-
-
//递归方法实现回溯
-
//输入：源数组 matrix， 行数 rows， 列数 cols，目标字符串 str，遍历深度 pathLength，标记数组 visited
-
//输出：有目标路径 true, 无解 false
-
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited)
-
{
-
-
//1.递归结束条件，找到目标路径，回溯结束
-
if(str[pathLength] == '\0')
-
return true;
-
-
bool hasPath = false;
-
if(row >= 0 && row < rows && col >= 0 && col < cols
-
&& matrix[row * cols + col] == str[pathLength]
-
&& !visited[row * cols + col])
-
{//1.递归判断条件，继续递归or返回结果
-
++pathLength;
-
visited[row * cols + col] = true;
-
-
//2.递归公式，从可选项中找出符合条件的选项，进行下一次递归
-
hasPath = hasPathCore(matrix, rows, cols, row, col - 1,
-
str, pathLength, visited)
-
|| hasPathCore(matrix, rows, cols, row - 1, col,
-
str, pathLength, visited)
-
|| hasPathCore(matrix, rows, cols, row, col + 1,
-
str, pathLength, visited)
-
|| hasPathCore(matrix, rows, cols, row + 1, col,
-
str, pathLength, visited);
-
-
if(!hasPath)
-
{//3.可选项中没有符合条件的结果，退回上一个步骤
-
--pathLength;
-
visited[row * cols + col] = false;
-
}
-
}
-
-
return hasPath;
-
}
-
-
//进行测试
-
void test01()
-
{
-
const char* matrix = "ABTGCFCSJDEH";
-
const char* str = "BFCE";
-
-
if(hasPath(matrix, 3, 4, str) == true)
-
printf("Passed.\n");
-
else
-
printf("FAILED.\n");
-
}
-
-
int main(int argc, char const *argv[])
-
{
-
test01();
-
return 0;
-
}
运行结果
文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/feit2417/article/details/98305484
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）