具体是例如下图：
![《剑指offer》:[66]矩阵中的路径](http://p1.codesocang.com/uploads/allimg/c160630/14C2DQL0260-3QH.jpg)
解决方案：主要是用回溯法。首先任意选一个入口地址，也就是任选一个格子，如果格子中的字符ch和字符串中的第一个字符相等，则字符串向前移动一位，而在格子里我们在允许的条件下(col<cols && row<rows边界条件)可以向上下左右四个方向进行探索，比较，如果相等则继续向前；如果不等，则回溯到上一个结点的位置。重复这个过程知道找到一条路径包含目标字符串，否则没有该路径。
具体实现代码如下：
#include <iostream>
using namespace std;
char arr[17]="abcesfcsadeekong";
char strr[6]="bcced";
bool HasPathHelp(char array[],int col,int row,int cols,int rows, char *str,int &pathlength,bool *visited )
{
if(str[pathlength]=='\0')
return true;
bool haspath=false;
if(row>=0 && row<rows && col >=0 && col <cols
&& array[row*cols+col]==str[pathlength]
&& !visited[row*cols+col])
{
++pathlength;
visited[row*cols+col]=true;
haspath=HasPathHelp(array,col-1,row,cols,rows,str,pathlength,visited) //left
|| HasPathHelp(array,col,row-1,cols,rows,str,pathlength,visited) //up
|| HasPathHelp(array,col+1,row,cols,rows,str,pathlength,visited) //right
|| HasPathHelp(array,col,row+1,cols,rows,str,pathlength,visited); //down
if(!haspath)
{
--pathlength;
visited[row*cols+col]=false;
}
}
return haspath;
}
bool HasPath(char array[],int rows, int cols,char *str)
{
if(array==NULL || rows<1 || cols<1 || str==NULL)
return false;
bool *visited=new bool[rows*cols];
memset(visited,0,rows*cols);
int pathlength=0;
for(int row=0;row<rows;row++)
{
for(int col=0;col<cols;col++)
{
if(HasPathHelp(array,col,row,cols,rows,str,pathlength,visited))
return true;
}
}
delete []visited;
return false;
}
int main()
{
bool result=HasPath(arr,4,4,strr);
if(result)
cout<<"该矩阵"<<arr<<"包含"<<strr<<"字符串"<<endl;
else
cout<<"该矩阵"<<arr<<"不包含"<<strr<<"字符串"<<endl;
system("pause");
return 0;
}
运行结果：
![《剑指offer》:[66]矩阵中的路径](http://p1.codesocang.com/uploads/allimg/c160630/14C2DQ950W0-49626.jpg)
- 顶
- 0
- 踩
- 0