矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；

样例
matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

回溯

时间复杂度O(n^2)

   在矩阵中任选一点为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。
   如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。
   在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要回到第n-1个字符，重新定位第n个字符。
　 通过设置布尔值矩阵标识出路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，
　 从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符。
　 如果4个相邻的格子都没有匹配字符串中下一个的字符，需要回到前一个重新定位。
　 重复这个过程，直至找出全部正确的路径。
class Solution {
    public boolean hasPath(char[][] matrix, String str) {
        if(matrix == null||str==null){
            return false;}
        int rows = matrix.length;
        if(rows==0)return false;
        int cols = matrix[0].length;

        int pathLength = 0;
        boolean[][] visited = new boolean[rows][cols];

        for(int i=0;i<rows;i++){
            for(int j = 0;j<cols;j++){
                if(hasPathCore(matrix,rows,cols,i,j,str,pathLength,visited))
                    return true;
            }
        }
        return false;
    }
    public boolean hasPathCore(char[][] matrix,int rows, int cols,int row, int col,
                               String str,int pathLength, boolean[][] visited){
        boolean flag = false;
        if(row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col] && matrix[row][col] == str.charAt(pathLength)){
            pathLength++;
            visited[row][col]=true;
            if(pathLength==str.length()){
                return true;
            }
            flag = hasPathCore(matrix, rows, cols, row+1, col, str, pathLength, visited)||
                hasPathCore(matrix, rows, cols, row, col+1, str, pathLength, visited)||
                hasPathCore(matrix, rows, cols, row-1, col, str, pathLength, visited)||
                hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited);
            if(!flag){
                pathLength--;
                visited[row][col]=false;
            }
        }
        return flag;
    }
}