题解 | #矩阵中的路径#

回溯法

    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if (word == null || word.length() == 0 || matrix == null || matrix.length == 0){
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[][] isVisited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (matrix[i][j] == word.charAt(0) && dfs(matrix,word,isVisited,i,j)){
                    return true;
                }
            }
        }

        return false;
    }

    private int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    private boolean dfs(char[][] matrix, String word,boolean[][] isVisted,int row,int col){

        if (word.length() == 0){
            return true;
        }

        if (row >= matrix.length || row < 0
                || col >= matrix[0].length || col < 0
                || isVisted[row][col] || word.charAt(0) != matrix[row][col]){
            return false;
        }

        isVisted[row][col] = true;

        for (int[] dir : dirs) {

            if (dfs(matrix,word.substring(1),isVisted,row+dir[0],col+dir[1])){
                return true;
            }

        }
        // 回溯时的状态清除
        isVisted[row][col] = false;
        return false;
    }