设计一个函数判断一个矩阵中是否存在一条包含某字符串中所有字符的路径。路径可以从矩阵任一格开始，每一步向上、下、左、右移动一格。
思路：回溯法
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(matrix == NULL || rows<1 || cols<1 || str == NULL);
bool visited[rows*cols];
memset(visited, 0, rows*cols);
int path_length = 0;
for(int row=0; row<rows; ++row)
for(int col=0; col<cols; ++col)
if(hasPathHelper(matrix, rows, cols, row, col, str, path_length, visited))
return true;
return false;
}
bool hasPathHelper(char* matrix, int rows, int cols, int row, int col, char* str, int& path_length, bool* visited)
{
if(str[path_length] == '\0')
return true;
bool has_path = false;
if(row>=0 && row<rows && col>=0
&& col<cols && matrix[row*cols+col] == str[path_length]
&& !visited[row*cols+col])
{
++path_length;
visited[row*cols+col] = true;
has_path = hasPathHelper(matrix, rows, cols, row, col-1, str, path_length, visited)
||hasPathHelper(matrix, rows, cols, row-1, col, str, path_length, visited)||
hasPathHelper(matrix, rows, cols, row, col+1, str, path_length, visited)||
hasPathHelper(matrix, rows, cols, row+1, col, str, path_length, visited);
if(!has_path)
{
--path_length;
visited[row*cols+col] = true;
}
}
return has_path;
}
