回溯法之矩阵中的路径

1.本题知识点

回溯法，矩阵

2. 题目描述

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

3. 思路

① 遍历矩阵，找到与路径第一个字符str[0]相同的矩阵元素m；

② 遍历m相邻的上、下、左、右四个字符，如果有和路径下一个字符str[1]相同的字符，则它就是下一次遍历的起点；若没有，回退(回溯)到上一个字符，重新遍历。

③ 需要用一个路径数组记录走过的矩阵元素，避免路径重复。

此题还是有些难度，建议先跑通代码，再加深理解。

Java版本：

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //参数校验
        if(matrix == null || rows < 1 || cols < 1 || str == null) return false;
        
        int index_path = 0;//路径数组的索引
        boolean [] table = new boolean[matrix.length];//记录矩阵中走路的痕迹表，防止重叠
        //遍历矩阵
        for(int row = 0 ; row < rows; row++){
            for(int col = 0;col < cols ; col++){
                //如果有这样的路径，返回true
                if(helper(matrix,rows,cols,row,col,str,index_path,table)){
                    return true;
                }
            }
        }
        return false;
    }

    boolean helper(char[] matrix, int rows, int cols,int row,int col, 
                    char[] str,int index_path,boolean [] table){
        //终止条件
        if(index_path == str.length ) return true;
        
        int index_matrix = row * cols + col;//用矩阵行列表示的矩阵元素在数组中的位置
        boolean hasPath = false;
        //---------这个if条件其实是在验证当前步走的是否正确
        if(row >= 0 && row < rows && col >=0 && col < cols 
           //当前步走的临时正确(如果下一步不对，当前步就不对)，即矩阵元素同路径元素相等
           && matrix[index_matrix] == str[index_path] 
           && !table[index_matrix]) //矩阵痕迹表中未走过
        {
            //--------下面其实是在验证下一步是否正确，即下一元素是否相等
            index_path++;//
            table[index_matrix] = true;//更新当前步为true
            hasPath = helper(matrix,rows,cols,row-1,col,str,index_path,table)//上
                   || helper(matrix,rows,cols,row+1,col,str,index_path,table)//下
                   || helper(matrix,rows,cols,row,col-1,str,index_path,table)//左
                   || helper(matrix,rows,cols,row,col+1,str,index_path,table);//右
            //如果上下左右都不能匹配下一个元素
            if(!hasPath)
            {
                //要回退到当前步,也就是说当前步走的不对，return false
                index_path--;
                //更新当前步为false
                table[index_matrix] = false;
            }
        }
        
        return hasPath;
    }
}