题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 A B T G C F C S J D E H
// 参数：原始数组，二维数组行，列，当前访问元素的行，列， // 目标字符串，访问标志，路径索引
bool isHavePath(const char *matrix, int rows, int cols, int i, int j, const char *str, bool *visited, int& pathlength) { if (str[pathlength] == '\0') return true; // 匹配结束，返回true bool havepath = false; // 答案 // 当前访问元素的行列没有越界，没有访问过，值和目标字符串对应位置一样 if (i >= 0 && i < rows && j >= 0 && j < cols && !visited[i * cols + j] && matrix[i * cols + j] == str[pathlength]) { visited[i * cols + j] = true; // 设置访问过 ++pathlength; // 注意：c++对于引用类型，不能传临时变量 // 也就是说，下面递归调用不能传pathlength+1 havepath = isHavePath(matrix, rows, cols, i - 1, j, str, visited, pathlength ) || isHavePath(matrix, rows, cols, i, j - 1, str, visited, pathlength ) || isHavePath(matrix, rows, cols, i + 1, j, str, visited, pathlength ) || isHavePath(matrix, rows, cols, i, j + 1, str, visited, pathlength ); if (!havepath) { // 没有找到，回溯，把访问标记和路径索引回溯-1 visited[i * cols + j] = false; --pathlength; } } return havepath; } bool hasPath(const char *matrix, int rows, int cols,const char *str) { if (matrix == NULL || rows <= 0 || cols <= 0 || str == NULL) return false; bool *visited = new bool(rows * cols); // 访问标志初始化 memset(visited, 0, rows * cols); int path = 0; for (int i = 0; i < rows; ++i) { // 遍历二维数组每一个元素 for (int j = 0; j < cols; ++j) { // path = 0; 这个可写可不写，因为如果匹配失败，在上面递归函数里，// path会回溯-1，直到减回0；匹配 成功直接返回了 if (isHavePath(matrix, rows, cols, i, j, str, visited, path)) // 递归 { delete []visited; return true; } } } delete []visited; return false; }