题目描述
- 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
- 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
- 如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
-
例如，在下面的 3 X 4 矩阵中包含一条字符串 "bfce" 的路径，但是矩阵中不包含"abfb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
题目解读
解题思路
回溯法- 思路一：和课本思路一致，将二维矩阵放入一维数组中，
以后推荐这种思想
因为用二维数组处理时，涉及辅助函数传递参数时不方便
- 思路二：和思路一思想一致只是里面实现代码有些许差别，特此提出，以供思考
- 思路三：和课本思路一致，将二维矩阵放入二维数组中
代码
- 思路一：和课本思路一致，将二维矩阵放入一维数组中
两套代码实现，第一套代码更加优越，仔细看代码哦
class Solution {
public:
bool core(char* matrix, int& rows, int& cols, char* str, int& len,
int *visit, int i, int j, int index){
bool flag = false;
if(str[index] == matrix[i * cols + j]){
visit[i * cols + j] = 1;
++index;
}
else{
return false;
}
if(index == len){
flag = true;
}
// 向上
if(flag == false && i-1>=0 && visit[(i-1)*cols + j] == 0){
flag = core(matrix, rows, cols, str, len, visit, i-1, j, index);
}
// 向下
if(flag == false && i+1<rows && visit[(i+1)*cols + j] == 0){
flag = core(matrix, rows, cols, str, len, visit, i+1, j, index);
}
// 向左
if(flag == false && j-1>=0 && visit[i*cols + j-1] == 0){
flag = core(matrix, rows, cols, str, len, visit, i, j-1, index);
}
// 向右
if(flag == false && j+1<cols && visit[i*cols + j+1] == 0){
flag = core(matrix, rows, cols, str, len, visit, i, j+1, index);
}
return flag;
}
void init_visit(int *visit, int size){
for(int i=0; i < size; ++i){
visit[i] = 0;
}
}
bool hasPath(char* matrix, int rows, int cols, char* str){
int len = strlen(str);
int visit[rows * cols];
int index = 0;
init_visit(visit, rows * cols);
for(int i=0; i < rows; ++i){
for(int j=0; j < cols; ++j){
cout << matrix[i * cols + j] << endl;
if(core(matrix, rows, cols, str, len, visit, i, j, index)){
return true;
}
init_visit(visit, rows * cols);
}
}
return false;
}
};
#include<iostream>
#include<cstring>
using namespace std;
class Solution {
public:
bool hasPathCore(int row, int col, int rows, int cols, char *matrix, int *visited, char* str, int length){
bool shang, xia, zuo, you;
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){
shang = hasPathCore(row-1, col, rows, cols, matrix, visited, str, length);
}else{
shang = false;
}
// 下
if(row < rows-1 && visited[(row+1) * cols + col]==0){
xia = hasPathCore(row+1, col, rows, cols, matrix, visited, str, length);
}else{
xia = false;
}
// 左
if(col > 0 && visited[row * cols + col-1]==0){
zuo = hasPathCore(row, col-1, rows, cols, matrix, visited, str, length);
}else{
zuo = false;
}
// 右
if(col < cols-1 && visited[row * cols + col+1]==0){
you = hasPathCore(row, col+1, rows, cols, matrix, visited, str, length);
}else{
you = false;
}
if(shang || xia || zuo || you){
return true;
}
}
return false;
}
void init_visited(int *visited, int size){
for(int i=0; i < size; i++){
visited[i] = 0;
}
}
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;
}
};
int main(){
Solution ss;
char str[20] = "bfce";
// char str[20] = "AAAAAAAAAAAA";
int rows = 3;
int cols = 4;
char matrix[rows * cols] = {'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h'};
// char matrix[rows * cols] = {'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'};
bool bb;
bb = ss.hasPath(matrix, rows, cols, str);
cout<<bb<<endl;
}
- 思路二代码 ，和思路一思想一致只是里面实现代码有些许差别，特此提出，以供思考
class Solution {
public:
bool hasPathCore(int row, int col, int rows, int cols, char *matrix, int *visited, char* str, int length){
bool shang=false, xia=false, zuo=false, you=false;
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){
shang = hasPathCore(row-1, col, rows, cols, matrix, visited, str, length);
}
// 下
if(row < rows-1 && visited[(row+1) * cols + col]==0){
xia = hasPathCore(row+1, col, rows, cols, matrix, visited, str, length);
}
// 左
if(col > 0 && visited[row * cols + col-1]==0){
zuo = hasPathCore(row, col-1, rows, cols, matrix, visited, str, length);
}
// 右
if(col < cols-1 && visited[row * cols + col+1]==0){
you = hasPathCore(row, col+1, rows, cols, matrix, visited, str, length);
}
if(shang || xia || zuo || you){
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];
// 将 visited 初始化为全0
memset(visited, 0, (rows*cols)*sizeof(int));
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)
memset(visited, 0, (rows*cols)*sizeof(int));
}
}
return false;
}
};
思路三代码
#include<iostream>
#include<cstring>
using namespace std;
#define rows 3
#define cols 4
class Solution {
public:
bool hasPathCore(int row, int col, char matrix[][cols], int visited[][cols], char* str, int length){
bool shang, xia, zuo, you;
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){
shang = hasPathCore(row-1, col, matrix, visited, str, length);
}else{
shang = false;
}
// 下
if(row < rows-1 && visited[row+1][col]==0){
xia = hasPathCore(row+1, col, matrix, visited, str, length);
}else{
xia = false;
}
// 左
if(col > 0 && visited[row][col-1]==0){
zuo = hasPathCore(row, col-1, matrix, visited, str, length);
}else{
zuo = false;
}
// 右
if(col < cols-1 && visited[row][col+1]==0){
you = hasPathCore(row, col+1, matrix, visited, str, length);
}else{
you = false;
}
if(shang || xia || zuo || you){
return true;
}
}
return false;
}
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 hasPath(char matrix[][cols], char* str){
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)){
return true;
}
init_visited(visited);
}
}
return false;
}
};
int main()
{
Solution ss;
char str[20] = "bfce";
char matrix[rows][cols] = {{'a', 'b', 't', 'g'}, {'c', 'f', 'c', 's'}, {'j', 'd', 'e', 'h'}};
// char str[20] = "AAAAAAAAAAAA";
// char matrix[rows][cols] = {{'A', 'A', 'A', 'A'}, {'A', 'A', 'A', 'A'}, {'A', 'A', 'A', 'A'}};
cout<<ss.hasPath(matrix, str)<<endl;
}
总结展望
