矩阵中的路径

矩阵中的路径

题目描述

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

解题思路

• 回溯法，使用一个标记数组来标记当前位置是否已访问
• 以每个位置为起点，递归遍历其四周，只要能访问且能匹配，就递归的访问下去，碰到当前路径走不下去，就重置标记数组，回退一步，直到有某条路径能走通

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,false,rows*cols);
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                //以每一个位置为起点，判断是否存在路径
                if(func(matrix,rows,cols,i,j,0,str,visited))//==true
                    return true;
            }
        }
        delete []visited;
        return false;
    }
    //i,j标记当前的位置；index标记当前已匹配的字符串的长度
    bool func(char* matrix, int rows, int cols,int i,int j,int index, char* str,bool* visited){
        //超过边界、当前字符不匹配、已经访问过
        if(i<0||j<0||i>=rows||j>=cols||matrix[i*cols+j]!=str[index]||visited[i*cols+j]==true)
            return false;
        //已经遍历完str
        if(index==strlen(str)-1) return true;
        //当前位置符合要求，置为已访问，并访问其四周
        visited[i*cols+j]=true;
        if(func(matrix,rows,cols,i+1,j,index+1,str,visited)||
           func(matrix,rows,cols,i,j+1,index+1,str,visited)||
           func(matrix,rows,cols,i-1,j,index+1,str,visited)||
           func(matrix,rows,cols,i,j-1,index+1,str,visited))
            return true;
        //当前位置的四周都失败了，则这个位置匹配的元素无效，要重新找
        //回溯就体现在对visited标记的恢复
        visited[i*cols+j]=false;
        return false;
    }
};