题目:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串"bfce”的路径(路径中的字母用下划线标出)。但矩阵中不包含字符串"abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子
完整代码:
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
//检查输入的合法性
if(matrix==nullptr ||rows<1 ||cols<1 ||str==nullptr)
return false;
//定义一个布尔矩阵,其大小和matrix一样,用来存放元素有没有访问过的标识
bool *Visited =new bool [rows*cols];
//用来初始化矩阵Visited所有元素即为0,即为false
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, str,Pathlength,Visited))
{
//删除辅助数组
delete[] Visited;
//返回匹配成功
return true;
}
}
}
//释放辅助空间
delete[] Visited;
//运行至此,说明匹配失败
return false;
}
private:
//调用匹配函数,从矩阵上的每一个点开始尝试匹配
bool hasPathCore(const char* matrix,int rows,int cols,int row,int col, const char* str,int&Pathlength,bool* Visited)
{
//如果已经匹配完整个字符序列,到结尾了
if(str[Pathlength]=='\0')
return true; //直接返回true,表示已经匹配完整个字符串
//记录该元素是否已经匹配过
bool hasPath=false;
//如果游标在合法范围内,且这个位置的值正好匹配,而且没有访问过
if(row>=0&&row<rows&&col>=0&&col<cols&&matrix[row*cols+col]==str[Pathlength]&&!Visited[row*cols+col])
{
//路径向前+1
++Pathlength;
//表示已经访问过
Visited[row*cols+col]=true;
//继续向前遍历,调用自身,分别从左/右/上/下匹配,只要有一个匹配成功,立即结束
hasPath=hasPathCore(matrix,rows,cols,row-1,col,str,Pathlength,Visited)
||hasPathCore(matrix,rows,cols,row+1,col,str,Pathlength,Visited)
||hasPathCore(matrix,rows,cols,row,col-1,str,Pathlength,Visited)
||hasPathCore(matrix,rows,cols,row,col+1,str,Pathlength,Visited);
//如果四个方向不存在匹配的字符,说明这个位置走错
if(!hasPath)
{
//先后倒退一步
--Pathlength;
Visited[row*cols+col]=false;
}
}
//返回这个位置是否匹配过
return hasPath;
}
};