矩阵中的路径问题详解回溯法

不多bb，直接上代码，见注释

public class BacktrackingAlgorithm {
    //剑指Offer，矩阵中的路径问题
    /*
     *总结：
     * 1. 回溯法的基本思路：递归+DFS
     * 2. 回溯法的模板见backtrackingAlgorithm方法
     * 2. 回溯法的典型问题：八皇后问题，迷宫问题
     */
    public static void main(String[] args) {
        //传入的matrix矩阵，以及行，列数
        char[] matrix = {'A', 'B', 'C', 'E', 'S', 'F','C','S','A','D','E','E'};
        int rows = 3;
        int cols = 4;
        //传入的字符串
        char[] str = {'A','B','C','C','E','D'};
        //使用hasPath表示矩阵中是否有符合str的路径
        boolean hasPath = false;
        if(str.length > 0){
            if(matrix.length > 0){
                int j = 0;
                int[] path = new int[str.length];
                for(int i=0;i<path.length;i++){
                    path[i] = -1;
                }
                for(int i=0;i<matrix.length;i++){
                    if(matrix[i] == str[j]){
                        hasPath = backtrackingAlgorithm(matrix,cols,str,path,i,j);
                        if (hasPath){
//                            return hasPath;
                            System.out.println("i：" + i + " ,hasPath：" + hasPath);
                        }
                    }
                }
//                return hasPath;
                System.out.println(hasPath);
            }else{
//                return hasPath;
                System.out.println(hasPath);
            }
        }else{
            //str长度为0，返回true
//            return true;
            System.out.println(true);
        }

    }

    //回溯法是深度优先策略的典型应用
    public static boolean backtrackingAlgorithm(char[] matrix, int cols, char[] str, int[] path, int i,int j){
        /*
         *回溯法的基本思路：
         *1. 判断递归终止条件：（1）找到符合问题的解，return（2）到达base问题，return
         *2. 不满足终止条件，将节点入栈，依次向下递归（使用循环）
         *3. 下一级递归未找到符合问题的解，回溯到上一级节点（节点出栈，return）
         *注意：
         *1. 回溯法需要辅助变量：使用栈/数组保存经过的节点路径，需要特别注意节点入栈和出栈的时机
         *2. 与一般递归相比，回溯法多了一步递归失败的回溯操作
         */

        //判断是否满足递归终止条件，需要特别注意的是，这些条件的出现顺序是固定的，不能交换位置
        //条件一：判断传入的数组下标是否越界
        if(i<0 || i>matrix.length-1){
            return false;
        }
        //条件二：判断节点是否已入栈，如果已入栈，则不可再访问
        for(int k=0;k<path.length;k++){
            if(i == path[k]){
                return false;
            }
        }
        //条件三：判断所以未i的matrix元素是否与索引为j的str元素相同
        if(matrix[i] != str[j]){
            return false;
        }
        //条件四：判断是否找到符合问题的解
        if(j==str.length-1){
            path[j] = i;
            return true;
        }


        //以上终止条件都不满足，将matrix下标入栈，继续向下递归
        path[j] = i;
        //向后递归
        if(backtrackingAlgorithm(matrix,cols,str,path,i+1,j+1)){
            return true;
        }
        //向前递归
        if(backtrackingAlgorithm(matrix,cols,str,path,i-1,j+1)){
            return true;
        }
        //向下递归
        if(backtrackingAlgorithm(matrix,cols,str,path,i+cols,j+1)){
            return true;
        }
        //向上递归
        if(backtrackingAlgorithm(matrix,cols,str,path,i-cols,j+1)){
            return true;
        }
        //下一级递归失败，找不到符合问题的解，节点出栈，并返回递归失败
        path[j] = -1;
        return false;
    }
}

以上均为个人见解，如有谬误，欢迎指正！