题解 | #矩阵中的路径#

通过回溯法，逐一尝试每个节点，并穷举每个节点的下一节点的可能性，使用递归完成每个节点的判断。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] target = word.toCharArray();
        int index = 0;
        
        boolean[][] used = new boolean[matrix.length][matrix[0].length];
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if(used[i][j] != true && matrix[i][j] == target[index]){
                    used[i][j] = true;
                    
                    if(index + 1 == target.length){
                        return true;
                    }
                    
                    boolean success = findNext(used, matrix, i, j, target, index+1);
                    if(success){
                        return true;
                    }else{
                        used[i][j] = false;
                    }
                }
            }
            
            
        }
        
        
        return false;
    }
    
    public boolean findNext(boolean[][] used, char[][] matrix, int i, int j, char[] target, int index){
        
        char res = target[index];
        
        if(i - 1 >= 0){
            if(used[i-1][j] != true && matrix[i-1][j] == res){
                
                if(index == target.length-1){
                    return true;
                }else{
                    used[i-1][j] = true;
                    boolean success = findNext(used, matrix, i-1, j, target, index + 1);
                    if(success){
                        return true;
                    }else{
                        used[i-1][j] = false;
                    }
                    
                }
            }
        }
        
        if(j - 1 >= 0){
            if(used[i][j-1] != true && matrix[i][j-1] == res){
                
                if(index == target.length-1){
                    return true;
                }else{
                    used[i][j-1] = true;
                    boolean success = findNext(used, matrix, i, j-1, target, index + 1);
                    if(success){
                        return true;
                    }else{
                        used[i][j-1] = false;
                    }
                }
            }
        }
        
        if(i + 1 < matrix.length){
            if(used[i+1][j] != true && matrix[i+1][j] == res){
                
                if(index == target.length-1){
                    return true;
                }else{
                    used[i+1][j] = true;
                    boolean success = findNext(used, matrix, i+1, j, target, index + 1);
                    if(success){
                        return true;
                    }else{
                        used[i+1][j] = false;
                    }
                    
                }
            }
        }
        
        if(j + 1 < matrix[i].length){
            if(used[i][j+1] != true && matrix[i][j+1] == res){
                
                if(index == target.length-1){
                    return true;
                }else{
                    used[i][j+1] = true;
                    boolean success = findNext(used, matrix, i, j+1, target, index + 1);
                    if(success){
                        return true;
                    }else{
                        used[i][j+1] = false;
                    }
                }
            }
        }
        
        return false;
    }
}