请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。 如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 注意： 输入的路径不为空； 所有出现的字符均为大写英文字母； 样例 matrix= [ [“A”,“B”,“C”,“E”], [“S”,“F”,“C”,“S”], [“A”,“D”,“E”,“E”] ] str=“BCCE” , return “true” str=“ASAE” , return “false”
思路： 用回溯的方法解决，从矩阵中任意一个位置出发，依次遍历。用nowPath标记遍历到的字符串的哪个位置，若字符串的nowPath上的位置与矩阵该位置上下左右位置上的字符相等，则继续往下遍历，若不相等，则后退一步，同时nowPath-1。
C++代码：
class Solution { public: bool hasPathFunction(vector<vector<char>>& matrix, int rows, int cols, int row, int col, string str, int nowPath, vector<vector<int>>& visited){ //循环终止的条件 if(str[nowPath] == '\0'){ return true; } //用来记录该位置是否符合条件 bool isPath = false; //判断row和col是否在矩阵中，并且矩阵中的元素是否等于字符串中某位置的元素，并且判断矩阵该位置上的元素是否访问过 if(row >= 0 && row < rows && col >= 0 && col < cols && matrix[row][col] == str[nowPath] && !visited[row][col]){ //标记该位置已经访问过，同时访问字符串的下一个位置 visited[row][col] = 1; nowPath++; //判断下一个位置 isPath = hasPathFunction(matrix, rows, cols, row - 1, col, str, nowPath, visited) || hasPathFunction(matrix, rows, cols, row + 1, col, str, nowPath, visited) || hasPathFunction(matrix, rows, cols, row, col - 1, str, nowPath, visited) || hasPathFunction(matrix, rows, cols, row, col + 1, str, nowPath, visited); //这部非常重要，若都不符合，后退一步 if(!isPath){ nowPath--; visited[row][col] = 0; } } return isPath; } bool hasPath(vector<vector<char>>& matrix, string str) { if(matrix.size() < 1 || matrix[0].size() < 1 || str.size() < 1){ return false; } int rows = matrix.size(); int cols = matrix[0].size(); ///用于标记该位置是否被访问过 vector<vector<int>> visited; for(int i = 0; i < rows; i++){ visited.push_back(vector<int>(matrix[i].size(), 0)); } //用来记录已经遍历到字符串的哪个一个位置 int nowPath = 0; for(int row = 0; row < rows; row++){ for(int col = 0; col < cols; col++){ if(hasPathFunction(matrix, rows, cols, row, col, str, nowPath, visited)){ return true; } } } return false; } };python代码：
class Solution(object): def hasPathFunction(self, matrix, rows, cols, row, col, string, nowPath, visited): if nowPath == len(string): return True hasPath = 0 if 0 <= row < rows and 0 <= col < cols and matrix[row][col] == string[nowPath] and not visited[row][col]: visited[row][col] = 1 nowPath += 1 hasPath = self.hasPathFunction(matrix, rows, cols, row - 1, col, string, nowPath, visited) or self.hasPathFunction(matrix, rows, cols, row + 1, col, string, nowPath, visited) or self.hasPathFunction(matrix, rows, cols, row, col - 1, string, nowPath, visited) or self.hasPathFunction(matrix, rows, cols, row, col + 1, string, nowPath, visited) if not hasPath: nowPath -= 1 visited[row][col] = 0 return hasPath def hasPath(self, matrix, string): """ :type matrix: List[List[str]] :type string: str :rtype: bool """ if len(matrix) < 1 or len(matrix[0]) < 1 or len(string) < 1: return False rows = len(matrix) cols = len(matrix[0]) visited = [[0] * cols for row in range(rows)] nowPath = 0 for row in range(rows): for col in range(cols): if self.hasPathFunction(matrix, rows, cols, row, col, string, nowPath, visited): return True return False