剑指offer（65）矩阵中的路径

public class Solution {
    //回溯法：使用回溯法，回溯法可以看作看成蛮力法的升级版，从解决问题的每一步的所有可能选项里系统地选出一个可行的解决方案，回溯法非常
    //适合由多个步骤组成的问题，并且每个步骤有多个选择，当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项，我们就这
    //重复选择，直至到达最终的状态
    
    //当矩阵中的坐标（row，col）的各自和路径字符串下标为strLength的字符一样时，从四个相邻的格子（row，col+1）（row，col-1）（row+1，col）（row-1，col）
    //中去定位路径字符串中下标为strLength+1的字符，如果4个方向相邻的各自都没有匹配字符串下标strLength+1的字符，则说明当前的字符在矩阵中的
    //定位不正确，我们需要回到上一个字符（strLength-1），然后重新定位，一直重复这个过程，直到路径字符串上的所有字符都在矩阵中找到合适的位置
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(matrix == null || matrix.length == 0 || rows <= 0 || cols <= 0 || str == null || str.length == 0 || matrix.length != rows * cols || rows * cols < str.length){
            return false;
        }
        boolean[] visited = new boolean[rows * cols];//设置矩阵中的每一个位置，默认都没访问过
        int strLength = 0;//路径字符串开始的位置
        for(int i = 0;i <= rows;i++){//遍历矩阵中的每一个位置
            for(int j = 0;j <= cols;j++){
                if(hasPathCore(matrix, rows, cols, str, i, j, visited, strLength)){
                    return true;
                }
            }
        }
    return false;
    }
    public boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, int row, int col, boolean[] visited, int strLength){
        boolean flag = false;
        //没访问过，并且与路径字符串中相等，考察下一个位置
        if(row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == str[strLength] && !visited[row * cols + col]){
            strLength++;
            visited[row * cols + col] = true;
            if(strLength == str.length)//已经匹配到最后，则返回true
                return true;
            //上下左右分别考察
            flag = hasPathCore(matrix, rows, cols, str, row, col + 1, visited, strLength) ||
                   hasPathCore(matrix, rows, cols, str, row, col - 1, visited, strLength) ||
                   hasPathCore(matrix, rows ,cols, str, row + 1, col, visited, strLength) ||
                   hasPathCore(matrix, rows, cols ,str, row - 1, col, visited, strLength);
            if(!flag){//如果下一个位置（上下左右）没有一个地方匹配，则当前路径节点在矩阵中的位置是不正确的，则回溯到上一个节点重新进行，并且将当前节点设置为没访问过
                strLength--;
                visited[row * cols + col] = false;
            }
        }
        return flag;
    }

}