题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子
例如：在下面的3x4的矩阵中包含一条字符串“bfce”的路径。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子
a b t g
c f c s
j d e h
分析
这是一个可以用回溯法解决的典型问题。
首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为c，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是c，那么这个格子不可能在路径上的第i个位置。
如果路径上的第i个位置正好是c，那么到相邻的格子寻找路径上的第i+1个字符。除矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程，直到路径上所有字符都在矩阵中找到对应的位置。
由于回溯法的递归特性，路径可以被看成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这时候只好在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，所以还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识是否已经进入了每个格子
C++算法实现
#include <iostream>
using namespace std;
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,
const char *str, int &pathLength, bool *visited);
/**
@param matrix 矩阵
@param rows 行
@param cols 列
@param str 字符串
@return 是否找到对应的路径
*/
bool hasPath(const char *matrix, int rows, int cols, const char *str)
{
// 处理异常情况
if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr) {
return false;
}
// 创建一个布尔值矩阵记录所行走的格子
bool *visited = new bool[rows * cols];
memset(visited, 0, rows * cols);
// 路径长度
int pathLength = 0;
// 遍历矩阵即二维数组
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
// 查找字符串
if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)) {
return true;
}
}
}
// 删除数组，释放内存
delete [] visited;
return false;
}
/**
@param matrix 矩阵
@param rows 总共的行数
@param cols 总共的列数
@param row 当前行
@param col 当前列
@param str 字符串
@param pathLength 路径长度
@param visited 走过的格子矩阵
@return 是否查找到字符串
*/
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,
const char *str, int &pathLength, bool *visited)
{
// 判断字符串是否已经查找结束，如果是表示查找成功
if (str[pathLength] == '\0')
return true;
// 是否拥有路径
bool hasPath = false;
/*
1、保证查找的范围，即属于矩阵当中
2、判断矩阵中某一格子的值是否等于字符串中的值
3、必须是没有占据的格子
满足1，2，3继续下一个字符的查找
*/
if (row >= 0 && row < rows && col >= 0 && col < cols
&& matrix[row * cols + col] == str[pathLength]
&& !visited[row * cols + col])
{
// 路径长度加1指向下一个字符
++pathLength;
// 记录当前占据的格子
visited[row * cols + col] = true;
// 在当前位置的相邻格子进行查找
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)
{
--pathLength;
// 标记当前格子没有被占据
visited[row * cols + col] = false;
}
}
return hasPath;
}
当矩阵中坐标为 (row, col) 的元素和路径字符串 str 中下标为 pathLength 的字符相同时，从 4 个相邻的元素 (row, col - 1) (左)、(row - 1, col) (上)、(row, col + 1) (右)、(row + 1, col) (下) 中去搜索路径字符串中下标为 pathLength + 1 的字符
若 4 个相邻的元素都没有匹配字符串中下标为 pathLength + 1 的字符，则表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，则回到前一个字符 (下标为 pathLength - 1)，重新搜索
重复以上过程，直到路径字符串上的所有字符都在矩阵中找到合适的位置（此时str[pathLength =='\0']）
