牛客剑指offer--JZ12 矩阵中的路径

JZ12 矩阵中的路径

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 。。。。 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
数据范围：0≤n,m≤20 0 \le n,m \le 20\ 0≤n,m≤20 ,1≤len≤25 1\le len \le 25\ 1≤len≤25

示例1：

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],“abcced”
返回值：true

示例2：

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],“abcb”
返回值：false

题目分析：

1. dfs遍历：pb存入的是bool型的是否遍历数组矩阵a[][]当前元素，传入参数为矩阵数组、结果字符串、当前的坐标i和j，还有到达的层数index
2. dfs需要步骤–截止条件、候选节点。
3. 截止条件为已遍历到结果字符串的最后一位
4. 候选节点为未越界的上下左右坐标，并且满足条件!pb[x][y]&&p[x][y]==str[index]，就往下一层继续遍历

代码如下：

class Solution {
public:
    
    bool pb[26][26]={false};
    bool flag=false;
    bool hasPath(vector<vector<char> >& p, string str) {
        for(int i=0;i<p.size();i++){
            for(int j=0;j<p[0].size();j++){
                if(!pb[i][j]&&p[i][j]==str[0]){
                    pb[i][j]=true;
                    dfs(p,str,1,i,j);
                    pb[i][j]=false;
                    if(flag){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    void dfs(vector<vector<char> >& p, string str,int index,int i,int j){
        //截至条件
        if(flag==true||index==str.size()){
            flag=true;
            return;
        }
        
        //候选节点
        for(int x=i-1;x<=i+1;x++){
            for(int y=j-1;y<=j+1;y++){
                //筛选合法
                if((x==i-1&&y==j)||(x==i+1&&y==j)||(x==i&&y==j-1)||(x==i&&y==j+1)){
                    if(x>=0&&y>=0&&x<p.size()&&y<p[0].size()){
                        //最终筛选
                        if(!pb[x][y]&&p[x][y]==str[index]){
//                             cout<<str[index]<<" "<<x<<" "<<y<<endl;
                            pb[x][y]=true;
                            dfs(p,str,index+1,x,y);
                            pb[x][y]=false;
                        }
                    }
                }
            }
        }
        
    }
};