剑指 Offer（第2版）面试题 12：矩阵中的路径

剑指 Offer（第2版）面试题 12：矩阵中的路径

题目来源：23. 矩阵中的路径

解法1：回溯

回溯算法模板题。

我们先枚举单词的起点，然后依次枚举单词的每个字母。

过程中需要将已经使用过的字母改成一个特殊字母（‘*’），以避免重复使用字符，注意回溯是要把特殊字母改回原来的状态，这也是回溯算法的精髓。

代码：

class Solution
{
private:
	const int dx[4] = {-1, 0, 1, 0};
	const int dy[4] = {0, 1, 0, -1};

public:
	bool hasPath(vector<vector<char>> &matrix, string &str)
	{
		// 特判
		if (matrix.empty())
			return false;
		int m = matrix.size(), n = m ? matrix[0].size() : 0;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (backtracking(matrix, str, 0, i, j))
					return true;
		return false;
	}
	// 辅函数 - 回溯
	bool backtracking(vector<vector<char>> &matrix, string &str, int level, int x, int y)
	{
		if (matrix[x][y] != str[level])
			return false;
		if (level == str.size() - 1)
			return true;
		char c = matrix[x][y];
		matrix[x][y] = '*';
		for (int i = 0; i < 4; i++)
		{
			int r = x + dx[i], c = y + dy[i];
			if (r >= 0 && r < matrix.size() && c >= 0 && c < matrix[0].size())
				if (backtracking(matrix, str, level + 1, r, c))
					return true;
		}
		matrix[x][y] = c;
		return false;
	}
};

复杂度分析：

时间复杂度：O(m*n*3^k)，其中 m 和 n 分别是二维矩阵 matrix 的行数和列数。遍历二维矩阵 matrix 的每个元素，作为单词的起点，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有 3 种选择。

空间复杂度：O(1)。