题解 | #矩阵中的路径#

经典回溯法，注意成功出口在失败出口之前即可。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean backtrack(char[][]matrix,String word,int index,int i,int j){
        //回溯法求解
         if(index==word.length()){
            //成功的出口
            return true;
        }
        //搜索到边界了
        if(i<0||i>=matrix.length||j<0||j>=matrix[0].length) return false;

        if(word.charAt(index)=='&'){
            //已经搜索过了
            return false;
        }
        if(word.charAt(index)==matrix[i][j]){
            //当前字符匹配，搜索邻近结点
            char temp=matrix[i][j];
            //标记为已经搜索过
            matrix[i][j]='&';
            boolean res=backtrack(matrix,word,index+1,i-1,j)||
                    backtrack(matrix,word,index+1,i+1,j)||
                    backtrack(matrix,word,index+1,i,j-1)||
                    backtrack(matrix,word,index+1,i,j+1);
            //恢复
            matrix[i][j]=temp;
            return res;
        }
        return false;
    }

    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++)
                if(backtrack(matrix,word,0,i,j)){
                    return true;
                }
        }
        return false;
        
    }
}