《剑指offer》面试题 12：矩阵中的路径（C++实现）

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

A B T G

C F C S

J D E H

代码

#pragma once
#include <string>
// 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有
// 字符的路径。

// 回溯法==>递归
// 不能重复进入同一个格子==>布尔值矩阵
bool hasPath(char* matrix, int rows, int cols, char* str)
{
	if (matrix == nullptr || rows <= 0 || cols <= 0 || 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, pathLength, str, visited))
				return true;
		}
	}

	delete[] visited;	// 释放内存
	return false;
}

// 递归 核心代码
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, 
	int& pathLength, const char* str, bool* visited)
{
	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])// 字符相等且不是重复点
	{
		++pathLength;
		visited[row * cols + col] = true;

		/* 向4个方向进行递归 */
		hasPath = hasPathCore(matrix, rows, cols, row, col - 1, pathLength, str, visited) ||
			hasPathCore(matrix, rows, cols, row - 1, col, pathLength, str, visited) ||
			hasPathCore(matrix, rows, cols, row, col + 1, pathLength, str, visited) ||
			hasPathCore(matrix, rows, cols, row + 1, col, pathLength, str, visited);

		if (!hasPath)	// 这里体现回溯
		{
			--pathLength;
			visited[row * cols + col] = false;
		}
	}

	return hasPath;
}