题目
设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过矩阵的某一格，那么该路径不能再次进入该格子。
如下所示的3*4的矩阵中包含一条字符串“bfce”的路径，但不包含字符串“abfb”的路径，因为字符串第一个字符b占据矩阵的第一行第二个格子后，不能再次进入该格子。
image.png
解题思路
- 从矩阵的左上角作为路径的起点。
- 如果矩阵中某个格子的字符为‘a’，并且这个格子正好对应路径上的第i个字符。那么下一步就是到相邻格子寻找路径上的第i+1个字符。重复这个过程，直到路径上所有字符都在矩阵中找到相应的位置。
- 需要定义一个和字符矩阵同样大小的布尔值矩阵，来识别路径是否已经进入每个格子。
代码
- 将二维矩阵放入一维数组中
class Solution{
public:
void init_visited(int *visited,int size)
{
for(int i=0;i<size;i++)
{
visited[i] = 0;
}
}
bool hasPathCore(int row,int col,int rows,int cols,char *matrix,int *visited,char* str,int length)
{
bool up,down,left,right;
if(matrix[row*cols+col] == str[length])
{
visited[row*cols+col] = 1;
length+=1;
if(strlen(str) == length)
{
return true;
}
//向上找
if(row>0 && visited[(row-1)*cols+col] == 0)
{
up = hasPathCore(row-1,col,rows,cols,matrix,visited,str,length);
}
else
{
up = false;
}
//下
if(row < rows-1 && visited[(row+1)*cols+col] == 0)
{
down = hasPathCore(row+1,col,rows,cols,matrix,visited,str,length);
}
else
{
down = false;
}
//左
if(col > 0 && visited[row*cols+col-1] == 0)
{
left = hasPathCore(row,col-1,rows,cols,matrix,visited,str,length);
}
else
{
left = false;
}
//右
if(col < cols-1 && visited[row*cols+col+1] == 0)
{
right = hasPathCore(row,col+1,rows,cols,matrix,visited,str,length);
}
else
{
right = false;
}
//只要上下左右出现一个true就可以
if(up || down || left || right)
{
return true;
}
}
return false;
}
bool hasPath(char* matrix,int rows,int cols,char* str)
{
if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
{
return false;
}
int length = 0;
int visited[rows*cols]; //标识路径是否已进入每个格子
init_visited(visited,rows*cols);
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(hasPathCore(i,j,rows,cols,matrix,visited,str,length))
{
for(int k = 0;k < rows*cols;k++)
{
cout << visited[k] << " ";
}
cout << endl;
return true;
}
//消除在visited中上一个格子走过的路径(全部为0)
init_visited(visited,rows*cols);
}
}
return false;
}
};
- 直接定义二维数组
- 细节(这部分看不懂可以看下面Github中的完整代码)
二维数组做实参和一维数组做实参是一样的
flag = ss.hasPath(matrix,str)
但是做形参就不一样了。如果将二维数组作为参数传递给函数，那么在函数的参数声明中必须指明数组的列数，数组的行数没有太大关系，可以指定也可以不指定。因为函数调用时传递的是一个指针，它指向由行向量够成的一维数组。
bool hasPathCore(int row,int col,char matrix[][cols],int visited[][cols],char* str,int length)
class Solution{
public:
void init_visited(int visited[][cols])
{
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
visited[i][j]=0;
}
}
}
bool hasPathCore(int row,int col,char matrix[][cols],int visited[][cols],char* str,int length)
{
bool up,down,left,right;
if(matrix[row][col] == str[length])
{
visited[row][col] = 1;
length+=1;
if(strlen(str) == length)
{
return true;
}
//向上找
if(row>0 && visited[row-1][col] == 0)
{
up = hasPathCore(row-1,col,matrix,visited,str,length);
}
else
{
up = false;
}
//下
if(row < rows-1 && visited[row+1][col] == 0)
{
down = hasPathCore(row+1,col,matrix,visited,str,length);
}
else
{
down = false;
}
//左
if(col > 0 && visited[row][col-1] == 0)
{
left = hasPathCore(row,col-1,matrix,visited,str,length);
}
else
{
left = false;
}
//右
if(col < cols-1 && visited[row][col+1] == 0)
{
right = hasPathCore(row,col+1,matrix,visited,str,length);
}
else
{
right = false;
}
//只要上下左右出现一个true就可以
if(up || down || left || right)
{
return true;
}
}
return false;
}
bool hasPath(char matrix[][cols],char* str)
{
if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
{
return false;
}
int length = 0;
int visited[rows][cols]; //标识路径是否已进入每个格子
init_visited(visited);
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(hasPathCore(i,j,matrix,visited,str,length))
{
for(int k = 0;k < rows;k++)
{
for(int n = 0;n < cols;n++)
{
cout << visited[k][n] << " ";
}
cout << endl;
}
return true;
}
//消除在visited中上一个格子走过的路径(全部为0)
init_visited(visited);
}
}
return false;
}
};
网友评论