【剑指offer12】矩阵中的路径（回朔法）,C++实现

1.题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如，在下面的3x4的矩阵中包含一条字符串"bfce"的路径，但矩阵中不包含"abcb"路径。因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

2.思路

回朔法判断矩阵中是否有字符串bfce的思路：

首先，在矩阵中查找和字符串第一个字符相同的矩阵元素b。然后，遍历矩阵元素b的上下左右四个字符，如果有和字符串下一个字符相同的矩阵元素f，则遍历矩阵元素f的上下左右四个字符……；如果没有和字符串下一个字符相同的矩阵元素f，则退到上一个字符，重新遍历。为了避免路径重复，需要一个辅助矩阵来记录路径。

3.code

# 返回值：是否存在路径，bool类型

# 参数：matrix矩阵，rows矩阵行数，cols矩阵列数，str字符串

 class Solution {

 public:

     bool hasPath(char* matrix, int rows, int cols, char* str)

     {

         if(matrix == NULL || rows<1 || cols<1|| str ==NULL)// 边界条件

             return false;

         bool *visited = new bool[rows*cols];               // 创建路径数组

         memset(visited,0,rows*cols);                       // 清空路径数组

         int pathLength = 0;                                // 字符串下标

         int row = 0;                                       // 矩阵下标

         int col = 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)){

                     return true;

                 }

             }

         delete[] visited;                                  // 销毁路径数组

         return false;

     }

 private:

     // 递归实现回朔法

     bool hasPathCore(char* matrix,int rows,int cols,int row,int col,char* str,int &pathLength,bool* visited){

         // 矩阵存在字符串路径（递归出口）

         if(str[pathLength] == '\0'){

             return true;

         }

         bool hasPath = false;

         if(row >= 0 && row < rows && col >= 0 && col < cols  && matrix[row*cols+col] == str[pathLength] && !visited[row*cols+col]){

             ++pathLength;                 // 矩阵中找到元素str[pathLength]，应该找元素str[pathLength+1]

             visited[row*cols+col] = true; // 路径矩阵做标记

             // 查找矩阵坐标(row，col)上下左右是否存在与str[pathLength+1]相同的元素

             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);

             // 矩阵坐标(row，col)上下左右不存在与str[pathLength+1]相同的元素

             if(!hasPath){

                 --pathLength;                 // 条件不符合，还原为str[pathLength]

                 visited[row*cols+col] = false;// 条件不符合，标记数组标记row*cols+col为未被标记

             }

         }

         return hasPath;

     }

 };

巴特西

【剑指offer12】矩阵中的路径（回朔法）,C++实现

1.题目

2.思路

3.code

最新文章

热门文章