矩阵中的路径

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

思路

这是一个回溯法解决的典型题
基本思路:
0. 根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次

根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入hasPathCore
根据col和row先确定一维数组的位置，因为给定的matrix是一个一维数组
确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接false，说明这条路不通
若pathLength，就是待判定的字符串str的索引已经判断到了最后一位，此时说明是匹配成功的
下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到pathLength到达末尾或者不满足递归条件就停止。
走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。

实现

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
	if (matrix == null || rows < 1 || cols < 1 || str == null) {
		return false;
	}
	//标志位数组
	boolean[] isVisited = new boolean[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, isVisited))
				return true;
		}
	}
	return false;
}


private boolean hasPathCore(char[] matrix, int rows, int cols, int row, int col, char[] str, int pathLength,
							boolean[] isVisited) {
	//先根据col和row计算第一个元素转一位数组的位置
	int index = row * cols + col;
	//递归终止条件
	if (row < 0 || col < 0 || row >= rows || col >= cols ||
			matrix[index] != str[pathLength]//如果不匹配返回false
			|| isVisited[index] == true) {
		return false;
	}
	//若pathLength已经到str末尾,说明之前的匹配成功了,直接返回True即可
	if (pathLength == str.length - 1) {
		return true;
	}
	//表示已经走过了
	isVisited[index] = true;
	//回溯，递归寻找，每次找到了就给k加一，找不到，还原
	boolean hasPath = hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength + 1, isVisited)
			|| hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength + 1, isVisited)
			|| hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength + 1, isVisited)
			|| hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength + 1, isVisited);
	if (hasPath) {
		return true;
	}
	//走到这，说明这一条路不通，还原，再试其他的路径
	isVisited[index] = false;
	return false;
}

此解来自牛客网我去个地方啊非常感谢