算法1

(暴力枚举) $O(n^2)$

就是dfs状态转移
写了好几遍一直存在的问题就还是没有改正，还是dfs的状态转移不熟练
这里涉及两个状态恢复，

1. 向上下左右四个方向走的时候的状态恢复，在递归树上的状态相当于往下的四个分支，从分支回来需要进行状态转移。
2. 当这个矩阵上的数被往下找的时候是不能重复的，但是找完往它的上一个状态回溯的时候是需要将本身用过的状态进行改变的。

时间复杂度

参考文献

java 代码

class Solution {
    public boolean hasPath(char[][] matrix, String str) {
        if(matrix==null||matrix.length==0) return false;
        boolean vis[][] = new boolean[matrix.length][matrix[0].length];
        for(int  i =0;i<matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(dfs(i,j,matrix,0,str,vis)) return true;
            }
        }
        return false;
    }
    public boolean dfs(int x,int y,char[][] matrix,int u,String str,boolean[][] vis){
        if(u==str.length()) return true;
        if(str.charAt(u)!=matrix[x][y]) return false;
        vis[x][y]=true;
        int[] dx = new int[]{-1,0,1,0};
        int[] dy = new int[]{0,1,0,-1};
        for(int i =0;i<4;i++){
            x+=dx[i];
            y+=dy[i];
            if(x>=0&&x<matrix.length&&y>=0&&y<matrix[0].length&&!vis[x][y]&&dfs(x,y,matrix,u+1,str,vis)) return true;
            x =x-dx[i];
            y =y-dy[i];
        }
        //又是这个错误，这是结束状态，将自动返回前一个状态要将状态恢复
        vis[x][y]=false;
        return false;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla