DFS

思路：遍历二维矩阵中的每一个结点作为开始结点进行搜索，如果匹配成功就继续匹配，失败就结束
使用 index 表示当前匹配到了目标 str 的哪个位置
curN 表示当前已经匹配成功的个数
visit 数组用于记录当前位置是否访问过
递归结束条件：curN = str.length 时表示整个 str 都已经匹配成功

class Solution {

    public boolean flag = false;

    public boolean hasPath(char[][] matrix, String str) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }

        if(matrix.length == 1 && matrix[0].length == 1 && matrix[0][0] == str.charAt(0)){
            return true;
        }

        boolean[][] visit = new boolean[matrix.length + 10][matrix[0].length + 10];
        //遍历所有结点作为开始结点
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(dfs(matrix, str, i, j, 0, 0, visit)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] matrix, String str, int x, int y, int curN, int index, boolean[][] visit){
        //越界就退出
        if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length){
            return false;
        }

        //整个str已经匹配完毕
        if(curN == str.length()){
            return true;
        }

        char c = str.charAt(index);
        if(matrix[x][y] == c && !visit[x][y]){//当字符可匹配并且此位置没有被访问过
            visit[x][y] = true;//标记位已访问
            boolean f = dfs(matrix, str, x, y - 1, curN + 1, index + 1, visit) ||
            dfs(matrix, str, x, y + 1, curN + 1, index + 1, visit) ||
            dfs(matrix, str, x - 1, y, curN + 1, index + 1, visit) ||
            dfs(matrix, str, x + 1, y, curN + 1, index + 1, visit);
            if(f){
                return true;
            }
            visit[x][y] = false;//回溯
        }


        return false;
    }
}