题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
#include <iostream>
#include <vector>
using namespace std;
void dfc(vector<vector<char> > strmat,vector<vector<bool> > mmat,
int i,int j,char *str,int pos,bool &m){
int row=strmat.size();
int col=strmat[0].size();
if(m==false){
if(str[pos+1]=='\0')
m=true;
else{
if(i-1>=0&&str[pos+1]==strmat[i-1][j]&&mmat[i-1][j]==0){ //上遍历
mmat[i-1][j]=1;
dfc(strmat,mmat,i-1,j,str,pos+1,m);
}
if(i+1<row&&str[pos+1]==strmat[i+1][j]&&mmat[i+1][j]==0){ //下遍历
mmat[i+1][j]=1;
dfc(strmat,mmat,i+1,j,str,pos+1,m);
}
if(j-1>=0&&str[pos+1]==strmat[i][j-1]&&mmat[i][j-1]==0){ //左遍历
mmat[i][j-1]=1;
dfc(strmat,mmat,i,j-1,str,pos+1,m);
}
if(j+1<col&&str[pos+1]==strmat[i][j+1]&&mmat[i][j+1]==0){ //右遍历
mmat[i][j+1]=1;
dfc(strmat,mmat,i,j+1,str,pos+1,m);
}
}
}
}
bool hasPath(char* matrix, int rows, int cols, char* str){
vector<vector<char> > strmat;
vector<vector<bool> > mmat;
vector<vector<int> > vecpos;
for(int i=0;i<rows;i++){
vector<char> tc;
vector<bool> tm;
for(int j=0;j<cols;j++){
char c=matrix[i*cols+j];
tc.push_back(c);
tm.push_back(0);
if(c==str[0]){
vector<int> tp;
tp.push_back(i); //行
tp.push_back(j); //列
vecpos.push_back(tp);
}
}
strmat.push_back(tc);
mmat.push_back(tm);
}
bool m=false;
int s=vecpos.size();
for(int i=0;i<s;i++){
mmat[vecpos[i][0]][vecpos[i][1]]=true;
dfc(strmat,mmat,vecpos[i][0],vecpos[i][1],str,0,m);
mmat[vecpos[i][0]][vecpos[i][1]]=false;
if(m)
return 1;
}
return 0;
}
int main(){
//char matrix[]="abcesfcsadee";
//char str[]="bcced";
//char str[]="abcb";
//char matrix[]="ABCESFCSADEE";
//char str[]="ABCCED";
char matrix[]="ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";
char str[]="SGGFIECVAASABCEHJIGQEMS";
hasPath(matrix,5,8,str);
system("pause");
}