65.矩阵中的路径.md

65.矩阵中的路径

题目描述

• 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如$ \begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ \end{bmatrix} $矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

 

解题思路

设置一个二维数组，用来保存哪些位置已经搜索过了，一维数组其实也行，因为给的数组实际上就是一维的，只不过给了行数和列数。然后遍历整个输入数组，找到所有第一个字符的位置（也可以在遍历过程中每找到一个起始字符就调用函数搜索匹配一次），然后依次从这些字符的位置开始调用函数递归搜索，成功匹配就把标志数组中相应位置置为true，继续搜索下一个位置，否则向上递归将标志数组改回false，第一个起始字符的位置如果都无法完整匹配的话再从下一个起始字符的位置开始匹配。

 

代码

• C++

class Solution {
private:
    bool search(char* flagMat, char* matrix, int rows, int cols, int row, int column, char* str){
        if(str[0]=='\0') return true;
        int idx = row*cols+column;
        if(row<0 || column<0 || row>=rows || column>=cols || flagMat[idx]) return false;
        
        if(matrix[idx] == str[0]){
            flagMat[idx] = 1;
            if(
                search(flagMat, matrix, rows, cols, row+1, column, str+1) || 
                search(flagMat, matrix, rows, cols, row-1, column, str+1) || 
                search(flagMat, matrix, rows, cols, row, column+1, str+1) || 
                search(flagMat, matrix, rows, cols, row, column-1, str+1)
              ) return true;
            flagMat[idx] = 0;
        }
        return false;
    }
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(str==NULL) return false;
        // 使用vector数组的话可以声明的时候就初始化，
        // 但是使用数组的话需要手动初始化，因为使用变量作为数组大小的时候无法在声明时初始化
        // vector<char> flagMat(rows*cols, 0);  // 初始化为全0，其实vector默认就初始化为0
        char flagMat[rows*cols]; // 变量名作为数组大小时无法在声明时赋值
        memset(flagMat, 0, rows*cols); // 初始化为全0，必须初始化
        for(int row=0; row<rows; row++){
            for(int column=0; column<cols; column++){
                int idx = row*cols+column;
                if(matrix[idx] == str[0]){
                    if(search(flagMat, matrix, rows, cols, row, column, str)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};